動態計画整理(二)

10058 ワード

ダイナミック？プログラム

このブログはOJのテーマをキャリアとして続けています.ダイナミック企画のテーマを整理します.
続々と更新します.
これは動的企画テーマの整理の二番目のブログです.最初のブログの住所は下記の通りです.http://blog.csdn.net/hjd_love_zzt/articale/detail/26979313
三、他のいくつかはDPを使って解決する問題です.
1、HDU 2084
テーマと分析:
DPを用いて解決される問題の特徴は、問題の最適解は、サブ問題の最適解を含むことである.


  
    
   
          。                 ，      ，        ，        。 
  
    
  
    
   
                                              ，                        。   ，                              。         。             。    2，              19      。       ，      ，    。       。 
  
    
  
    
   
      
  
    
  
    
   
       ，        DP 。                    ，          ，        DP     。

/*
 * HDU_2084.cpp
 *
 *  Created on: 2014 6 17 
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 105;
int num[maxn][maxn];

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);

		int i;
		int j;
		for(i = 1 ; i <= n ; ++i){
			for(j = 1 ; j <= i ; ++j){
				scanf("%d",&num[i][j]);
			}
		}

		int dp[n+1];
		for(i = 1 ; i <= n ; ++i){//       DP 
			dp[i] = num[n][i];
		}

		for(i = n-1 ; i >= 1 ; --i){//        
			for(j = 1 ; j <= i ; ++j){
				dp[j] = max(dp[j] + num[i][j],dp[j+1] +num[i][j]);
			}
		}

		printf("%d
",dp[1]);
	}

	return 0;
}

四、DPを使って最長の連続子と問題を解決する.
問題記述叙述:a[1]、a[2]…a[n]にa[i]、a[i＋1]、a[j-1]、a[j]を見つけてa[i]＋a[i＋1]＋a[J-1]＋a[j]を最大にする.
①最も簡単な最もeasuryは定義に基づいて列挙することを思い付きます.上下界｛i,j|0｝を列挙して、maxの値を維持すればいいです.中に上下界を列挙する時間の複雑さはO(n^2)で、区間との複雑さを求めるのはO(n)ですので、総時間の複雑さはO(n^3)です.

for ( int i = 1 ; i <= n ; i++ )//i          
    for ( int j = i ; j <= n ; j++ )//j          
        ans = max(ans,accumulate(a+i,a+j+1,0));

②実は第一の方法の最適化です.ここには非常にeasyが考えている最適化があります.すなわち、プレフィックスとsum[i]=a[0]+a[1]+…+a[i-1]+a[i]を前処理して、区間を計算すると、区間との複雑度をO(1)に下げることができます.列挙の上下界の複雑度は変わりません.従って総時間の複雑度はO(n^2)である.

for ( int i = 1 ; i <= n ; i++ )
    sum[i]=sum[i-1]+a[i];
for ( int i = 1 ; i <= n ; i++ )
    for ( int j = i ; j <= n ; j++ )
        ans = max(ans,sum[j]-sum[i-1]);

③ダイナミックプランニングの思考を利用して最適化を継続し、線形アルゴリズムを得ることができる.最大連続区間と標準アルゴリズムによってmaxn[i]がiで終わる最大連続と定義されている場合、非常easyは配達関係を見出す.maxn[i]=max｛0,maxn[i-1]＋a[i]である.だから、一回だけスキャンしてもいいです.総時間の複雑度はO(n)です.

for ( int i = 1 ; i <= n ; i++ )
{
    last = max(0,last)+a[i];//last                   
    ans = max(ans,last);//ans             
}

④同じように、似たような思考を用いる.まず、プレフィックスとsum[i]も前処理しなければならず、ans=max｛sum[i]-min｛sum[j]｝1240<=j<=n｝を押し出すことができる.また、最小プレフィックスとは、動的に維持することができる.従って全時間の複雑さはO(n)である.

for ( int i = 1 ; i <= n ; i++ )
    sum[i]=sum[i-1]+a[i];
for ( int i = 1 ; i <= n ; i++ )
{
    ans = max(ans,sum[i]-minn);
    minn = min(minn,sum[i]);
}

まとめ:シンプルなO(n^3)とプレフィックスと最適化したO(n^2)のアルゴリズムは非常にeasuryであるが、コードの実現はかえって法三のトラブルである.第4の方法は方法3と同じ複雑さがあるにもかかわらず、前処理と多く出るO(n)の空間が必要である.方法三は非常に良くて、非常に強いです.例題:1、NYOJ 44テーマ分析:この問題は抽象的にa[1]…a[n]を与えることです.a[i]、a[i＋1]…a[j-1]、a[j]を求めます.a[i]＋a[i＋1]＋a[j-1]＋a[j]を最大にする.この最大値を出力すればいいです.この問題は典型的なテーマです.アルゴリズムを提示します.(いずれも3つの方法を採用しています.)しかし、実現には異なる2つの解法があります.1)

/*
 * NYOJ_44.cpp
 *
 *  Created on: 2014 6 22 
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1000005;
int a[maxn];


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);

		int i;
		for(i = 1 ; i <= n ; ++i){
			scanf("%d",&a[i]);
		}

		int last = a[1];
		int ans = a[1];
		for(i = 2 ; i <= n ; ++i){
			last = max(0,last) + a[i];//last:  a[i]         
			ans = max(last,ans);//ans:        
		}

		printf("%d
",ans);
	}

	return 0;
}

、

/*
 * NYOJ_44.cpp
 *
 *  Created on: 2014 6 22 
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 1000005;
int a[maxn];

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);

		int pre;
		int cur;
		scanf("%d",&pre);

		int max = pre;
		int i;
		for(i = 1 ; i < n ; ++i){
			scanf("%d",&cur);

			if((cur+pre) > cur){
				cur += pre;
			}
			if(cur > max){
				max = cur;
			}

			pre = cur;
		}

		printf("%d
",max);
	}

	return 0;
}

、NYOJ 104のテーマを分析します.この問題は上記と違って、2次元の長男シーケンスの連続和を求めるところにあります.上記は1次元の最長男シーケンスの連続と…本題の鍵は2次元の問題を一方的な問題に転換して解決することです.最大サブ行列の結果が、r行目からk行目までの、i列目からj列目までのサブ行列である場合.例えば、以下に見られる(a rはa[r][i]を表し、配列下付きが1から始まる場合): | a 11…a 1 i…a 1 j…a 1 n| | a 21…a 2 i…a 2 j…a 2 n| | . . . . . . . | | . . . . . . . | | ar 1…ar…arj…arn| | . . . . . . . | | . . . . . . . | | ak 1…aki…akj…akn𞓜 | . . . . . . . | | an 1…ani…anj…ann| r行目からk行目までの各行を同じ列に加算して、1次元配列を例えば以下のように得ることができる. (ar 1＋…＋ak 1、ar 2＋…＋ak 2、…、arn＋…＋akn) これにより、最後に求められるのはこの一次元配列の最大サブセグメントと問題であることが分かります.これにより、問題を上の問題に転化しました.コードは例えば以下の通りです.

/*
 * NYOJ_104.cpp
 *
 *  Created on: 2014 6 22 
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 105;
int a[maxn][maxn];
int ans;

int n,m;

/**
 *   k         
 */
int work(int k){
	int j;

	int last = a[k][1];
	int ansn = a[k][1];
	for(j = 2 ; j <= m ; ++j){
		last = max(0,last) + a[k][j];
		ansn = max(last,ansn);
	}

	return ansn;
}

int main(){

	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);

		int i;
		int j;
		for(i = 1 ; i <= n ; ++i){
			for(j = 1 ; j <= m ; ++j){
				scanf("%d",&a[i][j]);
			}
		}

		ans = -1000;
		int k;
		for(i = 1; i <= n ; ++i){
			ans = max(ans,work(i));//                    
			for(j = i+1 ; j <= n ; ++j){
				for(k = 1 ; k <= m ; ++k){
					a[i][k] += a[j][k];//             ..
				}
				ans = max(ans,work(i));
			}

		}

		printf("%d
",ans);
	}

	return 0;

}

3、POJ 1050のテーマ分析:この問題は上の問題と似ています.入力データが違っているだけです.(行列はn＊mからn＊nに変わりました.他のものは同じです.)…

/*
 * POJ_1050.cpp
 *
 *  Created on: 2014 6 23 
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 105;

int a[maxn][maxn];

int n;
int ans;

int work(int k){
	int last = a[k][1];
	int ansn = a[k][1];

	int j;
	for(j = 2 ; j <= n ; ++j){
		last = max(0,last) + a[k][j];
		ansn = max(last,ansn);
	}

	return ansn;
}


int main(){
	while(scanf("%d",&n)!=EOF){
		int i;
		int j;
		for(i = 1 ; i <= n ; ++i){
			for(j = 1 ; j <= n ; ++j){
				scanf("%d",&a[i][j]);
			}
		}

		ans = -100000;
		int k;
		for(i = 1 ; i <= n ; ++i){
			ans = max(ans,work(i));

			for(j = i+1 ; j <= n ; ++j){
				for(k = 1 ; k <= n ; ++k){
					a[i][k] += a[j][k];
				}

				ans = max(ans,work(i));
			}
		}

		printf("%d
",ans);
	}

	return 0;
}

4、HDU 1231のテーマと分析:この問題は抽象的に見ると、やはり「最長連続サブシーケンスの和」です.前の問題とは違います.

/*
 * HDU_1231.cpp
 *
 *  Created on: 2014 6 23 
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 10005;

int a[maxn];//        
int ans[maxn];//ans[i]   a[i]            
int start[maxn];// a[i]              

int n;

int main(){
	while(scanf("%d",&n),n){

		int i;
		for(i = 1 ; i <= n ; ++i){
			scanf("%d",&a[i]);
		}

		ans[1] = a[1];
		start[1] = a[1];
		for(i = 2 ; i <= n ; ++i){
			if(ans[i-1] + a[i] > a[i]){
				ans[i] = ans[i-1] + a[i];
				start[i] = start[i-1];//   a[i]                a[i-1]                  
			}else{
				ans[i] = a[i];
				start[i] = a[i];// a[i]               a[i]  
			}
		}

		int ansn = -100000;
		int pos = -1;
		for(i = 1 ; i <= n ; ++i){
			if(ans[i] > ansn){
				ansn = ans[i];
				pos = i;
			}
		}

		if(ansn >= 0){
			printf("%d %d %d
",ansn,start[pos],a[pos]);
		}else{
			printf("%d %d %d
",0,a[1],a[n]);
		}
	}

	return 0;
}

著作権声明:このブログのオリジナル文章、ブログは、同意なしに、転載してはいけません.

JavaScriptでは一つの関数を実行してから次の関数を実行したいですか?