转自：http://blog.csdn.net/hyqsblog/article/details/46288923

这就是未来费用吗。。那人的代码真好

  

UVA10559 Blocks

#include<iostream> #include<string> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> #include<iomanip> #include<queue> #include<map> #include<set> #include<vector> #include<cstdlib> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define sf scanf #define pf printf #define LL long long #define bug1 printf("bug1\n"); const int INF=1e9; const int N=205; const int M=60000; const int inf=0x3f3f3f3f; int A[N]; int n; int dp[N][N][N]; int dfs(int i,int j,int k){ if(i>j)return 0; int &ret=dp[i][j][k]; if(ret!=-1)return ret; int p=j; while(p>=i&&A[p]==A[j]) p--; ret=max(ret,dfs(i,p,0)+(j-p+k)*(j-p+k)); for(int q=i;q<=p;++q){ if(A[q]!=A[q+1]&&A[q]==A[j]){ ret=max(ret,dfs(i,q,j-p+k)+dfs(q+1,p,0));// }// 原本漏了+k } return ret; } int main(){ int T; int cas=0; sf("%d",&T); while(T--){ sf("%d",&n); mem(dp,-1); for(int i=1;i<=n;++i)sf("%d",&A[i]); pf("Case %d: %d\n",++cas,dfs(1,n,0)); } }