낙곡[동태계획3]구간과 환형동태계획

79918 단어 낙곡제동적 기획
문제 목록 링크
P1220 가로등 끄기
  • "알고리즘 경연 시작 클래식(S e c o n d E d i t i o n) P 293 U V a 1336(Second\Edition)\P293\UVa 1336(Second Edition) P293 UVa 1336"
  • 참조
  • 임의의 시간에 꺼진 등은 반드시 연속적인 구간이다
  • f[i] [j] [k] f[i] [j] [k] f[i] [j] [k] 표시등 [i, j] [i, j] [i, j], 그리고 현재 위치는 kk, k=0k=0k=0은 왼쪽에 i, k=1k=1k=1k=1k=1k=1은 오른쪽 끝에 j
  • f [ i ] [ j ] [ 0 ] = m i n ( f [ i + 1 ] [ j ] [ 0 ] + ( p o s [ i + 1 ] − p o s [ i ] ) ∗ ( s u m [ i ] + s u m [ n ] − s u m [ j ] ) , f [ i + 1 ] [ j ] [ 1 ] + ( a [ j ] − a [ i ] ) ∗ ( s u m [ i ] + s u m [ n ] − s u m [ j ] ) ) ; f[i][j][0] = min ( f[i+1][j][0] + ( pos[i+1] - pos[i] ) * ( sum[i] + sum[n] - sum[j] ) , f[i+1][j][1] + ( a[j]-a[i] ) * ( sum[i]+sum[n]-sum[j]) ); f[i][j][0]=min(f[i+1][j][0]+(pos[i+1]−pos[i])∗(sum[i]+sum[n]−sum[j]),f[i+1][j][1]+(a[j]−a[i])∗(sum[i]+sum[n]−sum[j]));
  • f [ i ] [ j ] [ 1 ] = m i n ( f [ i ] [ j − 1 ] [ 0 ] + ( p o s [ j ] − p o s [ i ] ) ∗ ( s u m [ i − 1 ] + s u m [ n ] − s u m [ j − 1 ] ) , f [ i ] [ j − 1 ] [ 1 ] + ( a [ j ] − a [ j − 1 ] ) ∗ ( s u m [ i − 1 ] + s u m [ n ] − s u m [ j − 1 ] ) ) ; f[i][j][1] = min ( f[i][j-1][0] + ( pos[j] - pos[i] ) * ( sum[i-1] + sum[n] - sum[j-1] ) , f[i][j-1][1] + ( a[j]-a[j-1] ) * ( sum[i-1] + sum[n] - sum[j-1] ) ); f[i][j][1]=min(f[i][j−1][0]+(pos[j]−pos[i])∗(sum[i−1]+sum[n]−sum[j−1]),f[i][j−1][1]+(a[j]−a[j−1])∗(sum[i−1]+sum[n]−sum[j−1]));
  • #include
    #include
    #include
    using namespace std;
    int n,c,f[60][60][2],sum[60],inf=1e7;
    struct lamp{
    	int p,c;
    }s[60];
    int main(){
    	cin>>n>>c;
    	for(int i=1;i<=n;i++){
    		cin>>s[i].p>>s[i].c;
    		sum[i]=sum[i-1]+s[i].c;		
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			f[i][j][0]=f[i][j][1]=inf;
    		}
    	}	
    	f[c][c][0]=f[c][c][1]=0; 
    	for(int len=2;len<=n;len++){
    		for(int i=1;i+len-1<=n;i++){
    			int j=i+len-1;
    			f[i][j][0]=min(f[i+1][j][0]+(s[i+1].p-s[i].p)*(sum[n]-(sum[j]-sum[i])),
    						   f[i+1][j][1]+(s[j].p-s[i].p)*(sum[n]-(sum[j]-sum[i])));
    			f[i][j][1]=min(f[i][j-1][0]+(s[j].p-s[i].p)*(sum[n]-(sum[j-1]-sum[i-1])),
    						   f[i][j-1][1]+(s[j].p-s[j-1].p)*(sum[n]-(sum[j-1]-sum[i-1])));
    		}
    	}
    	cout<<min(f[1][n][0],f[1][n][1])<<endl;
    } 
    

    P3205 [HNOI2010] 합창팀
  • f[i] [j] [k] f[i] [j] [k] f[i] [j] [k] 표시 구간 [i, j] [i, j]의 방안 수, k=0k=0k=0일 때 왼쪽에서 넣고, k=1k=1k=1일 때 오른쪽에서 넣는다.
  • f [ i ] [ j ] [ 0 ] + = f [ i + 1 ] [ j ] [ 0 ] , h [ i ] < h [ i + 1 ] f[i][j][0]+=f[i+1][j][0],h[i]f[i][j][0]+=f[i+1][j][0],h[i]
  • f [ i ] [ j ] [ 0 ] + = f [ i + 1 ] [ j ] [ 1 ] , h [ i ] < h [ j ] f[i][j][0]+=f[i+1][j][1],h[i]f[i][j][0]+=f[i+1][j][1],h[i]
  • f [ i ] [ j ] [ 1 ] + = f [ i ] [ j − 1 ] [ 0 ] , h [ j ] > h [ i ] f[i][j][1]+=f[i][j-1][0],h[j]>h[i] f[i][j][1]+=f[i][j−1][0],h[j]>h[i]
  • f [ i ] [ j ] [ 1 ] + = f [ i ] [ j − 1 ] [ 1 ] , h [ j ] > h [ j − 1 ] f[i][j][1]+=f[i][j-1][1],h[j]>h[j-1] f[i][j][1]+=f[i][j−1][1],h[j]>h[j−1]
  • 한 사람만 있을 때 방안은 하나입니다. 기본적으로 왼쪽에서 가입하고 초기화할 때 f [i] [i] [0] = 1 f [i] [i] [0] = 1 f [i] [i] [0] = 1
  • #include
    #include
    using namespace std;
    int n,h[1010],mod=19650827,f[1010][1010][2];
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>h[i];
    		f[i][i][0]=1;
    	}
    	for(int len=1;len<=n;len++){
    		for(int i=1;i+len-1<=n;i++){
    			int j=i+len-1;
    			if(h[i]<h[i+1]) f[i][j][0]+=f[i+1][j][0];
    			if(h[i]<h[j]) f[i][j][0]+=f[i+1][j][1];
    			if(h[j]>h[j-1]) f[i][j][1]+=f[i][j-1][1];
    			if(h[j]>h[i]) f[i][j][1]+=f[i][j-1][0];
    			f[i][j][0]%=mod;f[i][j][1]%=mod;
    		}
    	}
    	cout<<(f[1][n][0]+f[1][n][1])%mod<<endl;
    } 
    

    P1880 [NOI1995] 스톤 결합
  • 고리를 체인으로 분해
  • f[i] [j] f[i] [j] f[i] [j]는 구간 [i, j] [i, j]의 최대 득점, g[i] [j] g[i] [j] g[i] [j] 구간 [i, j] [i, j] [i, j]의 최소 득점
  • 을 나타낸다.
  • f [ i ] [ j ] = s u m [ i ] [ j ] + m a x ( f [ i ] [ k ] + f [ k + 1 ] [ j ] ) , i ≤ k < j f[i][j]=sum[i][j]+max(f[i][k]+f[k+1][j]),i\leq kf[i][j]=sum[i][j]+max(f[i][k]+f[k+1][j]),i≤k
  • g [ i ] [ j ] = s u m [ i ] [ j ] + m i n ( g [ i ] [ k ] + g [ k + 1 ] [ j ] ) , i ≤ k < j g[i][j]=sum[i][j]+min(g[i][k]+g[k+1][j]),i\leq kg[i][j]=sum[i][j]+min(g[i][k]+g[k+1][j]),i≤k
    #include
    #include
    using namespace std;
    int n,a[210],sum[210],f[210][210],g[210][210],inf=1e9,maxans,minans=inf;
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		a[n+i]=a[i];
    	}
    	for(int i=1;i<=2*n-1;i++){
    		sum[i]=sum[i-1]+a[i];
    	}
    	for(int len=2;len<=n;len++){
    		for(int i=1;i+len-1<=2*n-1;i++){
    			int j=i+len-1;
    			g[i][j]=inf;
    			for(int k=i;k<j;k++){
    				f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
    				g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]+sum[j]-sum[i-1]);	
    			}			
    		} 
    	}
    	for(int i=1;i<=n;i++){
    		maxans=max(maxans,f[i][i+n-1]);
    		minans=min(minans,g[i][i+n-1]); 
    	}
    	cout<<minans<<endl<<maxans<<endl;	
    } 
    

    P1063 기운 목걸이
  • f [ i ] [ j ] = h e a d [ i ] ∗ h e a d [ k + 1 ] ∗ h e a d [ j ] + m a x ( f [ i ] [ k ] + f [ k + 1 ] [ j ] ) f[i][j]=head[i]*head[k+1]*head[j]+max(f[i][k]+f[k+1][j]) f[i][j]=head[i]∗head[k+1]∗head[j]+max(f[i][k]+f[k+1][j])
  • #include
    #include
    using namespace std;
    int head[300],f[300][300];
    int n,ans;
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>head[i];
    		head[n+i]=head[i];
    	} 
    	for(int len=1;len<=n;len++){
    		for(int i=1;i+len-1<=2*n-1;i++){
    			int j=i+len-1;
    			for(int k=i;k<j;k++){
    				f[i][j]=max(f[i][j],head[i]*head[k+1]*head[j+1]+f[i][k]+f[k+1][j]);
    			}
    			ans=max(ans,f[i][j]);
    		}
    	}	
    	cout<<ans<<endl;
    } 
    

    P1005 매트릭스 취수 게임(60점)
  • 각 줄은 독립적이며 각 줄의 최대 화합을 단독으로 구하면 된다.
  • dp[i][j]dp[i][j]dp[i][j]는 구간 [i, j][i, j][i, j]가 선택되지 않은 최대치
  • 를 나타낸다
  • d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + 2 m − ( j − i ) + 1 ∗ a [ i − 1 ] , d p [ i ] [ j + 1 ] ∗ 2 m − ( j − i ) + 1 ∗ a [ j + 1 ] ) dp[i][j]=max(dp[i-1][j]+2^{m-(j-i)+1}*a[i-1],dp[i][j+1]*2^{m-(j-i)+1}*a[j+1]) dp[i][j]=max(dp[i−1][j]+2m−(j−i)+1∗a[i−1],dp[i][j+1]∗2m−(j−i)+1∗a[j+1])
  • #include
    #include
    #include
    using namespace std;
    int n,m,a[90];
    long long dp[90][90],sum,ans;
    long long quick_pow(long long a,long long x){
    	long long ans=1;
    	while(x){
    		if(x&1) ans=ans*a;
    		a=a*a;
    		x>>=1;
    	}
    	return ans;
    }
    int main(){
    	cin>>n>>m;
    	while(n--){
    		memset(dp,0,sizeof dp);
    		ans=0;
    		for(int i=1;i<=m;i++) cin>>a[i];
    		for(int i=1;i<=m;i++){
    			for(int j=m;j>=i;j--){
    				long long x=quick_pow(2,m-(j-i)-1);
    				dp[i][j]=max(dp[i][j],max(dp[i-1][j]+x*a[i-1],dp[i][j+1]+x*a[j+1])); 
    			}
    		}
    		for(int i=1;i<=m;i++){
    			ans=max(ans,dp[i][i]+quick_pow(2,m)*a[i]);
    		}
    		sum+=ans;
    	}
    	cout<<sum<<endl;
    }
    

    P3146 [USACO16OPEN]248 G
  • f[i] [j] f[i] [j] f[i] [j]는 구간 [i, j] [i, j] [i, j]의 원소를 모두 합쳐서 얻은 최대 수치
  • 를 나타낸다
    #include
    #include
    using namespace std;
    int n,a[250],f[250][250],ans;
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];f[i][i]=a[i];
    	}
    	for(int len=2;len<=n;len++){
    		for(int i=1;i+len-1<=n;i++){
    			int j=i+len-1;
    			for(int k=i;k<j;k++){
    				if(f[i][k]==f[k+1][j]){
    					f[i][j]=max(f[i][j],f[i][k]+1);
    					ans=max(ans,f[i][j]);
    				}
    			}
    		}
    	}
    	cout<<ans<<endl;
    } 
    

    P4170 [CQOI2007] 페인팅
    [i] [j] [j] f[i] [j] [i] [i, j] [i, j] [i, j] f[i] f[i] [j] [i] [j] f[i] [i] [i, j] [i, j] [i, j] [i, j] [i,]의 최소 도색 횟수 f[i] [j] = f [i] [j] [j] = = = = = i = = = = j m i = [i] [j] [i] [i] [i] [i] [i] [i] [i] [j] [i] [j] [j] [f[i] [j] [j] [f[i] [j] [j] [j] [j] [j] [j] [j] [j] [{\begin{aligned} 1, i=j\min(f[i+1][j], f[i][j-1], s[i]=s[j]\min(f[i][k]+f[k+1][j]), k\in[i,j-1],s[i]eq s[j]\end{aligned}\right. f[i][j]=⎩⎪⎨⎪⎧​1,i==jmin(f[i+1][j],f[i][j−1],s[i]==s[j]min(f[i][k]+f[k+1][j]),k∈[i,j−1],s[i]​=s[j]​
    #include
    #include
    #include
    using namespace std;
    string s;
    int n,f[60][60],inf=1e9;
    int main(){
    	cin>>s;n=s.length();s.insert(0," ");
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			f[i][j]=inf;
    		}
    	} 
    	for(int i=1;i<=n;i++){
    		f[i][i]=1;
    	}
    	for(int len=2;len<=n;len++){
    		for(int i=1;i+len-1<=n;i++){
    			int j=i+len-1;			
    			if(s[i]==s[j]) f[i][j]=min(f[i+1][j],f[i][j-1]);
    			else{
    				for(int k=i;k<j;k++){
    					f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    				}
    			}
    		}
    	}
    	cout<<f[1][n]<<endl;
    } 
    

    CF607B Zuma
  • f[i][j]f[i][j]f[i][j]는 구간 [i,j][i,j][i,j]의 최소 합병 시간
  • 을 나타낸다
  • f [ i ] [ j ] = { f [ i + 1 ] [ j − 1 ] , a [ i ] = = a [ j ] m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) f[i][j]=\left\{\begin{aligned} f[i+1][j-1],a[i]==a[j]\\min(f[i][j],f[i][k]+f[k+1][j])\end{aligned}\right. f[i][j]={f[i+1][j−1],a[i]==a[j]min(f[i][j],f[i][k]+f[k+1][j])​
  • f[i] [i] = 1 f[i] [i] = 1 f[i] = 1, f [i] [i + 1] = = {1, a [i] = a [i + 1] 2, a [i] ≠ a [i + 1] f [i] [i+1] =\left\{\begin {aligned} 1, a[i] = a [i + 1]\2, a [i] eq a [i + 1]\agnendrighed} {{f[i][i+1]={1,a[i]==a[i+1]2,a[i]​=a[i+1]​
  • #include
    #include
    using namespace std;
    int n,a[600],f[600][600],inf=2e9;
    void init(){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			f[i][j]=inf;
    		}
    	}
    	for(int i=1;i<=n;i++){
    		f[i][i]=1;	
    	}
    	for(int i=1;i<n;i++){
    		if(a[i]==a[i+1]) f[i][i+1]=1;
    		else f[i][i+1]=2;
    	}		
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	init();
    	for(int len=3;len<=n;len++){
    		for(int i=1;i+len-1<=n;i++){
    			int j=i+len-1;
    			if(a[i]==a[j]) f[i][j]=f[i+1][j-1];
    			for(int k=i;k<j;k++)
    				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);						
    		}
    	}
    	cout<<f[1][n]<<endl;
    } 
    

    좋은 웹페이지 즐겨찾기