程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 3390 Print Words in Lines 動態規劃

poj 3390 Print Words in Lines 動態規劃

編輯:關於C++

題意:

給n個單詞的長度和每行最多能放的字符數m,每行產生的值為(m-x)^2,x是該行的字符數(包括單詞之間的空格),求把所有單詞放完產生的值的最小和。

分析:

動態規劃很重要的就是狀態的定義,在由子問題向父問題推進的過程中,定義的狀態要能對之前的所有情況進行總結,比如背包問題中dp[i][v]中的v,不管之前1~i-1個物品如何取捨,他們的總重量肯定在0~v之中,故每步能把指數級的問題線性化。這題也是,剛考慮第i個單詞時,前面所有單詞不管怎麼放最後一個的結束位置肯定在1~m之間,故定義dp[i][s](s<=m)表示放完前i個單詞第i個單詞末位位於該行s處的最小值。

代碼:

 

//poj 3390
//sep9
#include 
using namespace std;
const int maxM=108;
const int maxN=10004;
int dp[maxN+10][maxM+10];
int L[maxN];
int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		int m,n,s;
		scanf("%d%d",&m,&n);
		for(int i=1;i<=n;++i)
			scanf("%d",&L[i]);
		memset(dp,0x7f,sizeof(dp));
		dp[0][m]=0;
		for(int i=1;i<=n;++i){
			int x=dp[maxN][maxM];
			for(s=m;s>=0;--s)
				x=min(x,dp[i-1][s]);	
			dp[i][L[i]]=x+(m-L[i])*(m-L[i]);
			for(s=L[i]+2;s<=m;++s){
				int x=s-L[i]-1;
				if(dp[i-1][x]==dp[maxN][maxM])
					continue;
				int y=dp[i-1][x]-(m-x)*(m-x)+(m-s)*(m-s);
				dp[i][s]=y;
			}
		}
		int ans=dp[0][maxM];
		for(s=0;s<=m;++s)
			ans=min(ans,dp[n][s]);
		printf("%d\n",ans);
	}
	return 0;	
} 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved