记录编号	298474	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.611 s
提交时间	2016-08-21 17:10:00	内存使用	94.14 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
long long dp[310][310][128],ans;
//dp[i][j][k]表示将区间[i,j]合并为k(低位优先)的最大得分 
int n,k,p,a[310],ch[310],v[310];
int main()
{
	freopen("merge_2016.in","r",stdin);
	freopen("merge_2016.out","w",stdout);
	scanf("%d%d",&n,&k);
	p=(1<<k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=0;i<p;i++) scanf("%d%d",&ch[i],&v[i]);
	//合并了0次的状态 
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	for (int s=0;s<p;s++)
		dp[i][j][s]=-99999999999999999ll;
	for (int i=1;i<=n;i++) dp[i][i][a[i]]=0;
	for (int l=2;l<=n;l++){//合并长度为l的式子 
		int len=(l-1)%(k-1)+1;//计算合并后的区间长度 
		if (len>1)//合并散点 
		for (int i=1;i<=n-l+1;i++){//枚举合并区间的左端点 
			int j=i+l-1;//计算右端点 
			for (int P=j-1;P>=i;P-=k-1)//每次向右合并一个当前长为1的区间 
			for (int s=0;s<(1<<len);s++)//枚举合并后状态 
			dp[i][j][s]=max(dp[i][j][s],dp[i][P][s>>1]+dp[P+1][j][s&1]);
		}
		else//表示再次进行了一次合并 
		for (int i=1;i<=n-l+1;i++){//枚举合并区间的左端点 
			int j=i+l-1;//计算右端点 
			for (int P=j-1;P>=i;P-=k-1)//每次向右合并一个当前长为1的区间 
			for (int s=0;s<p;s++)//枚举合并后状态，并把这个区间合并 
			dp[i][j][ch[s]]=max(dp[i][j][ch[s]],dp[i][P][s>>1]+dp[P+1][j][s&1]+v[s]);
		}
	}
	long long ans=0;
	for (int i=0;i<p;i++) ans=max(ans,dp[1][n][i]);
	printf("%lld\n",ans);
	return 0;
}