UVA - 10559 Blocks
最编程
2024-06-03 16:36:12
...
题文：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1500（或者见紫书）
题解：
因为这个题目我们用区间的dp常见套路设dp[i][j]表示处理到i~j的最大贡献不能靠枚举断点进行转移，所以我们要更细致的描述这个状态。设dp[i][j][k],表示把第i个区间和第j个区间合并，并且由于前面的消除有k个与区间j的颜色相同的方块接着j后面的最大贡献。
那么转移我们可以考虑1.直接将j区间和k消除。dp[i][j][k]=dp[i][j-1][0]+(len[j]+k)^2。2.考虑将j和前面的某个颜色相同的区间合并，所以要消除中间的某几段区间。
既：dp[l][r][k]=dp[i+1,][r-1][0]+dp[l][i][k+len[r]]。的确这个题目还是自己好好消化吧，是道经典的dp题目。
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> using namespace std; int color[1000],len[1000],n,t; int shu[1000],dp[300][300][300]; void cl(){ memset(color,0,sizeof(color)); memset(len,0,sizeof(len)); memset(shu,0,sizeof(shu)); memset(dp,0,sizeof(dp)); } int dfs(int l,int r,int k){ if(l>r) return 0; if(l==r) return (len[l]+k)*(len[l]+k); if(dp[l][r][k]!=0) return dp[l][r][k]; dp[l][r][k]=dfs(l,r-1,0)+(len[r]+k)*(len[r]+k); for(int i=l;i<r;i++){ if(color[i]==color[r]) dp[l][r][k]=max(dp[l][r][k],dfs(i+1,r-1,0)+dfs(l,i,k+len[r])); } return dp[l][r][k]; } int main(){ scanf("%d",&t); for(int hh=1;hh<=t;hh++){ scanf("%d",&n); cl(); for(int i=1;i<=n;i++) scanf("%d",&shu[i]); int star=1,now=1,num=0,lenn=0; while(now<=n){ while(shu[star]==shu[now]){ now++,lenn++; } color[++num]=shu[star]; len[num]=lenn; lenn=0;star=now; } printf("Case %d: %d\n",hh,dfs(1,num,0)); } }
上一篇： 使用Jmeter进行性能测试
下一篇： DP 系列] m 型背包