状态 memo[i][j] 表示从开始到第 i 个字符和从第 j 个字符到结尾两个字符串匹配需要的最小耗费。
状态转移可能有三种情况：
1. memo[i - 1][j] + cost[i]
2. memo[i][j + 1] + cost[j]
3. memo[i - 1][j + 1] (if str[i] == str[j])

注意：
1.只要保存单个字符删除或添加两者的最小值即可。
2.最终方案可能有一个中间字符，然后两边匹配，也可能没有中间字符，此时j = i + 1。

#include <cstdio>

#define MAXN 26
#define MAXM 2000
#define INT_MAX 2147483647
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

class DPer
{
public:
	void Ipt();
	int operator () ();
protected:
private:
	int _m, _n;
	int _mEnd;
	static int _memo[MAXM + 1][MAXM + 2];    // 注意这里第一维是 MAXM + 1 ，不是 MAXM + 2
	int _ls[MAXN];
	char _str[MAXM + 2];
};

int main()
{
	DPer dp;
	dp.Ipt();
	printf("%d", dp());
	return 0;
}

int DPer::_memo[MAXM + 1][MAXM + 2] = {0};

void DPer::Ipt()
{
	int i;
	scanf("%d%d%s", &_n, &_m, _str + 1);
	_mEnd = _m + 1;
	for (i = 1; i < _mEnd; ++i)
	{
		_str[i] -= 'a';
	}
	char c[2];
	int a, d;
	int *pA = &a, *pD = &d;
	for (i = 0; i < _n; ++i)
	{
		scanf("%s%d%d", c, pA, pD);
		_ls[c[0] - 'a'] = min(a, d);
	}
}

int DPer::operator () ()
{
	int res = INT_MAX;
	int i, j;
	int minSum[MAXM + 1];
	minSum[0] = 0;    // 先求出段最小耗费保存起来
	int sum = 0;
	for (i = 1; i < _mEnd; ++i)
	{
		sum += _ls[_str[i]];
		minSum[i] = sum;
	}
	for (i = 0; i < _mEnd; ++i)
	{
		_memo[i][_mEnd] = minSum[i];
		_memo[0][i + 1] = minSum[_m] - minSum[i];
	}
	int iEnd = _m;
	int op, minOp;
	for (i = 1; i < iEnd; ++i)
	{
		for (j = _m; j > i; --j)
		{
			op = _memo[i - 1][j] + _ls[_str[i]];
			minOp = op;
			op = _memo[i][j + 1] + _ls[_str[j]];
			minOp = min(minOp, op);
			if (_str[i] == _str[j])
			{
				op = _memo[i - 1][j + 1];
				minOp = min(minOp, op);
			}
			_memo[i][j] = minOp;
		}
	}
	for (i = 0; i < _m; ++i)
	{
		if (_memo[i][i + 1] < res)
		{
			res = _memo[i][i + 1];
		}
		if (_memo[i][i + 2] < res)
		{
			res = _memo[i][i + 2];
		}
	}
	if (_memo[_m][_mEnd] < res)
	{
		res = _memo[_m][_mEnd];
	}
	return res;
}

• Re:0ms这样办到的…… (11) heimengnan 2010-02-04 00:02:15