POJ 1390 Blocks 区间DP

区间DP的核心：把大区间分解成相同规模的小区间，小区间返回子结构的值给大区间从而得到最优解。但是怎么就能根据不同的题模拟出特定的比较合适的子结构呢？我觉得与其说这是一种编码的熟练度问题，不如说是对实际问题建模的敏感度问题。如何设计优秀的子结构问题真的很考验一个人的最基本最核心的创造力和分析能力，刷题套模板真的能整出来吗。。。

就拿这个题来说，可以很轻易的想到dp[i][j]为i到j区间的最优值，但是在分解成子问题的时候发现决策变了。比如 1 2 3 1 2 3 1（就本题 拉长两倍 数量不变）的情况下 dp[1][7] 可以很明显的分解成 dp[1][4] 和 dp[5][7] 但是三个1明显是需要一起合并的，那么就需要把父结构的信息(比如最右侧的1 ) 传递给子结构，方案改成 dp[1][4] 和 dp[]5[6],把最右侧的1传递给4所在位置的len，递归解决的时候就得给父结构传个0过去，在加一维为父结构传递过来的需要合并的数量，初始化的时候父结构传个0过去即可

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e2+10;
int dp[maxn][maxn][maxn],len[maxn],c[maxn],cnt;
int solve(int l,int r,int k)
{
	if(dp[l][r][k]) return dp[l][r][k];
	if(l==r) return (len[r]+k)*(len[r]+k);
	dp[l][r][k] = solve(l,r-1,0)+(len[r]+k)*(len[r]+k);
	for(int i = l; i < r; ++i) if(c[i]==c[r])
	dp[l][r][k] = max(dp[l][r][k],solve(l,i,len[r]+k)+solve(i+1,r-1,0));
	return dp[l][r][k];
}
int main()
{
	int cas = 0;
	int T; scanf("%d",&T);
	while(T--)
	{
		int pre = -1,cnt = 0;
		memset(len,0,sizeof(len));
		memset(dp,0,sizeof(dp));
		int n;scanf("%d",&n);
		for(int i = 1,x; i <= n; ++i)
		{
			scanf("%d",&x);
			if(x==pre) len[cnt]++;
			else
			{
				c[++cnt] = x; len[cnt]++; 
				pre = x;
			}
		}	
		printf("Case %d: %d\n",++cas,solve(1,cnt,0));
	}	
}