poj1390

/* solution: 区间dp,加状态参数。 如果只是用状态dp(i, j)来描述消去方块i到方块j获得的分数是无法形成递推关系的。 因为在这个时候对于最右边的大块有两种选择，一是直接消去，二是将其与左边某个大块 合并删除。而对于选择二来说，删去未必是最有方案，也许还应该与左边的某方块合并后 消去。所以只有两个参数是无法准确描述状态并形成递推关系的。解决方案就是“加参数” dp(i, j, k)表示消去方块i->j，同时j右边与j同色的方块长度（也称之为个数）为k 此时递推关系: 直接消去j: dp(i,j,len)=dp(i,j-1,0)+(seg[j].len+len)*(seg[j].len+len); 将j与左边某个方块k合并： dp(i,j,len)=dp(k+1,j-1,0)+dp(i,k,len[j]+len); note: 在选择方块序号k时注意循环边界处理 date: 2016/8/13 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 200 + 5; struct Segment { int color, len; Segment(int c, int l) : color(c), len(l) {} Segment() {} }; int block[maxn], n, d[maxn][maxn][maxn]; Segment seg[maxn]; //大块 bool deleted[maxn]; //表示下表为i的大块已经被消去了 int dp(int from, int to, int len) { //表示消去从from->to的大块，其中to右边有个长度为len的相同颜色的大块 if(d[from][to][len] != -1) return d[from][to][len]; if(from == to) return d[from][to][len] = (seg[to].len + len) * (seg[to].len + len); int ans = dp(from, to - 1, 0) + (seg[to].len + len) * (seg[to].len + len); for(int i = from; i < to; i++) { //在左边寻找一个与to颜色相同的大块消去，注意循环边界。 if(seg[i].color == seg[to].color) { ans = max(ans, dp(i+1, to-1, 0) + dp(from, i, seg[to].len + len)); } } return d[from][to][len] = ans; } int main() { //freopen("input.txt", "r", stdin); int T, kase = 0; scanf("%d", &T); while(T--) { memset(d, -1, sizeof(d)); scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &block[i]); int len = 0, dex = 0; seg[dex] = Segment(block[0], 1); for(int i = 1; i < n; i++) { if(block[i] == block[i-1]) seg[dex].len++; else seg[++dex] = Segment(block[i], 1); } printf("Case %d: %d\n", ++kase, dp(0, dex, 0)); } return 0; }