意甲冠军:
给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#includeusing 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; }