区间DP

区间DP常用模板

所有的DP问题，第一维都是枚举区间长度，第二维枚举起点，先求出小区间的属性值，进而扩展到大区间

for (int i = 1; i <= n; i++) {
    dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }

1、区间DP复习

2、石子合并

3、PKUpoj3280

题目描述：给定一个字符串，通过增加或删除相关字母形成回文串，每一个不同的字母增加和删除操作需要的花费不同，求形成回文串所需的最小代价

思路

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2010;
char s[N];
int n, m;
int cost[30];
int dp[N][N];//dp[i][j] 存储从 i 到 j 这一段转换成回文子序列需要的最小花费

int main() {
	ios::sync_with_stdio(false);//将stdio解除绑定,使得cin与scanf效率相差无几
	int a, b;
	char t;
	while (cin >> n >> m) {
		cin >> s + 1;
		while (n--) {
			cin >> t >> a >> b;
			cost[t - 'a'] = min(a, b);
		}
//		for (int i = m; i >= 1; i--) {
//			dp[i][i] = 0;
//			for (int j = i + 1; j <= m; j++) {
//				if (s[i] == s[j]) {
//					if (j - i <= 2)
//						dp[i][j] = 0;
//					else
//						dp[i][j] = dp[i + 1][j - 1];
//				} else
//					dp[i][j] = min(dp[i + 1][j] + cost[s[i] - 'a'], dp[i][j - 1] + cost[s[j] - 'a']);
//			}
//		}
		for (int i = 1; i <= m; i++)
			dp[i][i] = 0;
		for (int len = 2; len <= m; len++) // 长度,从短到长
			for (int i = 1; i + len - 1 <= m; i++) { // 起点
				int j = i + len - 1; // 终点
				if (s[i] == s[j]) {
					if (j - i <= 2)
						dp[i][j] = 0;
					else
						dp[i][j] = dp[i + 1][j - 1];
				} else {
					if (j - i <= 1)
						dp[i][j] = min(cost[s[i] - 'a'], cost[s[j] - 'a']);
					else
						dp[i][j] = min(dp[i + 1][j] + cost[s[i] - 'a'], dp[i][j - 1] + cost[s[j] - 'a']);
				}
			}

		printf("%d\n", dp[1][m]);
	}
	return 0;
}