4301538_ce.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 46 行

#include <stdio.h>
#include <string.h>

char str[2008];
int n, m;
int cost[256];
int dp[2008][2008];

int min(int a, int b)
{
	return a < b ? a : b;
}

int mincost(int st, int ed)
{
	if (st >= ed)
		return 0;
	if (dp[st][ed] != -1)
		return dp[st][ed];
	int ret = min(mincost(st + 1, ed) + cost[str[st]], mincost(st, ed - 1) + cost[str[ed]]);
	if (str[st] == str[ed])
	{
		ret = min(ret, mincost(st + 1, ed - 1));
	}
	return dp[st][ed] = ret;
}

int main()
{
	int a, b, i;
	char tmp[2];

	scanf("%d%d", &n, &m);
	scanf("%s", str);
	for (i = 0; i < n; i++)
	{
		scanf("%s%d%d", tmp, &a, &b);
		cost[tmp[0]] = min(a, b);
	}
	for (i = 0; i < m; i++)
	{
		memset(dp[i], -1, sizeof dp[i]);
	}
	printf("%d\n", mincost(0, m - 1));
	return 0;
}