数位DP 回文序列 POJ-3280 Cheapest Palindrome 题目链接：[ POJ - 3280 ] 题目大意 给定字符串s，长度为m，由n个小写字母组成。在s的任意位置增删字母，把它变成回文串，增删特定字母的花费不同，求最小花费 思路 定义状态 dp[i][j] 表示字符串s的子区间 s[i, j] 变成回文的最小花费 那么每次有三种情况: 如果 s[i] == s[j], 那么 dp[i][j] = dp[i + 1][j - 1]。 如果 dp[i + 1][j] 是回文串, 那么 dp[i][j] = dp[i + 1][j] + w[i]。 如果 dp[i][j - 1] 是回文串, 那么 dp[i][j] = dp[i][j - 1] + w[j]。 2, 3情况的状态转移方程就是 dp[i][j] = min(dp[i + 1][j] + w[i], dp[i][j - 1] + w[j]) 题解代码 #include<bits/stdc++.h> using namespace std; int w[30], dp[2010][2010]; char s[2010], ch; int n, m; int main(void) { int x, y; while (cin >> n >> m) { cin >> s; for (int i = 0; i < n; i++) { cin >> ch >> x >> y; w[ch - 'a'] = min(x, y); } for (int i = m - 1; i >= 0; i--) { // i是子区间的起点 for (int j = i + 1; j < m; j++) { // j是子区间的终点 if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = min(dp[i + 1][j] + w[s[i] - 'a'], dp[i][j - 1] + w[s[j] - 'a']); } } cout << dp[0][m - 1] << endl; } return 0; }

数位DP 石子合并 模板题 题目 有n堆石子排成一排，每堆石子有一定的数量，将n堆石子合并成一堆。合并的规则是每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数，求最小花费。 题解代码 #include<bits/stdc++.h> using namespace std; int sum[1010]; int dp[1010][1010], s[1010][1010]; int n, x; int main(void) { while (~scanf("%d", &n)) { sum[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &x); sum[i] = sum[i - 1] + x; } for (int i = 1; i <= n; i++) { dp[i][i] = 0; s[i][i] = i; } for (int len = 1; len < n; len++) { for (int i = 1; i <= n - len; i++) { int j = i + len; dp[i][j] = INF; for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) { if (dp[i][k] + dp[k + 1][j] + sum[j] - sum[i -1] < dp[i][j]) { dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]; s[i][j] = k; } } } } cout << dp[1][n] << endl; } return 0; }