题文：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
     
      #include
      
       #include
       
        #include
        
         #include
         
          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