方块消除

题目链接：luogu P2135

题目大意

给你一些数，每次你可以选一个数，它和它旁边一样的数就会被消掉，你会获得的的分数是这次消掉数的个数的平方。
要你最大化分数。

思路

这题其实就是 方块消除 Blocks 的弱化版。
只要改改代码，DP 一下就好了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int T, n, a[201], f[201][201][201];
int na[201], nm[201], nn, tmp;

int work(int i, int j, int k) {
	if (f[i][j][k]) return f[i][j][k];
	if (i == j) return (nm[i] + k) * (nm[i] + k);
	f[i][j][k] = work(i, j - 1, 0) + (nm[j] + k) * (nm[j] + k);
	for (int mid = i; mid < j; mid++)
		if (na[mid] == na[j])
			f[i][j][k] = max(f[i][j][k], work(i, mid, k + nm[j]) + work(mid + 1, j - 1, 0));
	return f[i][j][k];
}

int main() {
//	scanf("%d", &T);
//	while (T--) {
//		memset(f, 0, sizeof(f));
	
	scanf("%d", &nn);
	for (int i = 1; i <= nn; i++) scanf("%d", &na[i]);
	for (int i = 1; i <= nn; i++) scanf("%d", &nm[i]);
	
//		na[++nn] = a[1];
//		nm[nn] = 1;
//		for (int i = 2; i <= n; i++)
//			if (a[i] == a[i - 1]) nm[nn]++;
//				else {
//					na[++nn] = a[i];
//					nm[nn] = 1;
//				}
	
	printf("%d", work(1, nn, 0));
//	}
	
	return 0;
}