题意：
给定n个方块，相邻同色的方块可以消除，得分为消除的个数^2
问最高得分
dp[ l ][ r ][ k ] : 表示[l,r]区间内，消掉 [l,r)区间最高分 + 消掉[r, r+k] （[r,r+k]为同色）的最高分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
#define ll int
#define N 210
ll dp[N][N][N];//dp[l][r][k] 使得区间[l,r]为空时最高分 最后一次操作为将[r,r+k]个与r同色的块消掉
ll clo[N], n;
ll dfs(ll l, ll r, ll k){
if(l>r)return 0;
if(dp[l][r][k])return dp[l][r][k];
int ans = dfs(l,r-1,0) + (1+k)*(1+k);
for(int i = r-1; i >= l; i--)
if(clo[i] == clo[r])
ans = max(ans, dfs(l, i, k+1)+dfs(i+1,r-1,0));
return dp[l][r][k] = ans;
}
int main()
{
ll i, j, k, u, v, T, Cas = 1;scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(clo, -1, sizeof clo);
for(i = 1; i <= n; i++) scanf("%d",&clo[i]);
memset(dp, 0, sizeof dp);
printf("Case %d: %d\n",Cas++, dfs(1,n,0));
}
return 0;
}
/*
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1500
99
9
1 2 2 3 2 3 3 3 1
10
1 1 1 1 1 1 1 1 1 1
5
1 2 2 3 4
18
1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1
30
1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2
60
1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2
200
2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 3 2 3 2 3 2 2 2 3 3 3 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2
*/
Uva 10559 & POJ 1390 Blocks 区间dp,布布扣,bubuko.com
Uva 10559 & POJ 1390 Blocks 区间dp
原文：http://blog.csdn.net/acmmmm/article/details/24312967