记录编号	264928	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	C++	运行时间	1.886 s
提交时间	2016-05-31 16:14:43	内存使用	88.18 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
#define Menci 99999999999999LL
int N, K;
int trans[256];
int power[256];
int str[300];
long long f[300][300][128];
int main()
{
	freopen("merge_2016.in", "r", stdin);
	freopen("merge_2016.out", "w", stdout);
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i++)
		scanf("%1d", &str[i]);
	for (int i = 0; i < (1 << K); i++)
		scanf("%d%d", &trans[i], &power[i]);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			for (int k = 0; k < (1 << (K - 1)); k++)
				f[i][j][k] = -Menci;
	for (int i = 0; i < N; i++)
		f[i][i][str[i]] = 0;
	for (int l = 2; l <= N; l++)
	{
		int len = (l - 1) % (K - 1) + 1;
		if (len > 1)
		{
			for (int st = 0; st + l - 1 < N; st++)
			{
				int ed = st + l - 1;
				for (int cut = ed; cut > st; cut -= K - 1)
				{
					for (int x = 0; x < (1 << (len - 1)); x++)
						for (int y = 0; y < 2; y++)
							f[st][ed][(x << 1) + y] = max(f[st][ed][(x << 1) + y], f[st][cut - 1][x] + f[cut][ed][y]);
				}
			}
		}
		else
		{
			for (int st = 0; st + l - 1 < N; st++)
			{
				int ed = st + l - 1;
				for (int cut = ed; cut > st; cut -= K - 1)
				{
					for (int x = 0; x < (1 << (K - 1)); x++)
						for (int y = 0; y < 2; y++)
							f[st][ed][trans[(x << 1) + y]] = max(f[st][ed][trans[(x << 1) + y]], f[st][cut - 1][x] + f[cut][ed][y] + (long long)power[(x << 1) + y]);
				}
			}
		}
	}
	long long ans = 0;
	int len = (N - 1) % (K - 1) + 1;
	for (int i = 0; i < (1 << len); i++)
		ans = max(ans, f[0][N - 1][i]);
	printf("%lld\n", ans);
	return 0;
}