POJ 1390

好题

刚开学，很久没做，实在没有头绪，参考了别人的题解，就当找状态吧（惭愧）

题意：祖玛

思路：

• 最基础的，肯定将原数组进行处理，转化为关于线段的数组。
• 很容易想到的DP就是，考虑一段长度，问题是状态转移方程，需要先找出合适而有限无后效的状态，常规思路就是取出其中一个，不过这样做的问题有一个，就是取出一个线段后，其两端如果可以相连，那么这就不是一个无后效的操作了
• 无后效的解决，用了一个很精妙的思路考虑：因为一次状态转移的策略选择，可能会对线段数组中产生合并影响，那么干脆将这个可能的增量影响，记录为一个新的维度，具体怎么加待定
• 这样的问题仍然很大，这时候另一个简化出现了，我的状态转移中策略选择，只对所选线段区间的一段进行操作，并且，策略选择，只选择和一端相同的，这样的话，整个选择过程其实只有两种情况，一个是最大值成立需要所选择线段和最右端在后面出现连接，一个则刚好相反，没有这样的线段，一旦出现连接，我们是不可以更改原先的线段数组的，这样是有后效性的，这种情况，我们干脆把这个变化，记录为新的维度

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

const int maxn= 200+5;

int ar[maxn], lth[maxn], co[maxn];
int dp[maxn][maxn][maxn];

void Init()
{
	memset(ar, 0, sizeof(ar));
	memset(lth, 0, sizeof(lth));
	memset(co, -1, sizeof(co));
	memset(dp, -1, sizeof(dp));
}
int dfs(int l, int r, int dlt)
{
	if (-1!= dp[l][r][dlt]){
		return dp[l][r][dlt];
	}
	int tp= lth[r]+dlt;
	if (l== r){
		return tp*tp;
	}

	int maxs= tp*tp+dfs(l, r-1, 0);

	for (int i= l; i< r-1; ++i){
		if (co[r]!= co[i]){
			continue;
		}
		int psm= dfs(i+1, r-1, 0);
		int tsm= psm+dfs(l, i, dlt+lth[r]);

		if (tsm> maxs){
			maxs= tsm;
		}
	}

	return dp[l][r][dlt]= maxs;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	for (int i= 1; i<= t; ++i){
		scanf("%d", &n);

		Init();

		for (int j= 1; j<= n; ++j){
			scanf("%d", ar+j);
		}

		int pos= 0;
		for (int j= 1; j<= n; ++j){
			if (ar[j]!= ar[j-1]){
				++pos;
				co[pos]= ar[j];
				++lth[pos];
			}
			else{
				++lth[pos];
			}
		}

		int ans= dfs(1, pos, 0);
		printf("Case %d: %d
", i, ans);

	}

	return 0;
}