| 动态规划 | 背包问题 | poj1837,poj1276 |
| 型如下表的简单DP | poj3267,poj1836,poj2533, poj3176,poj1080,poj1159,poj1260 |
背包问题
poj 1837
题意：有一个棍子，从中间挂上。左右都有若干钩子（共C个），给出每个钩子离中心的距离。现在有G个砝码，要求把所有的砝码都挂上，并保持棍子平衡，问共有多少种情况
f[i][j] 表示前i个物品挂上以后偏移量为j时的情况数。。。最大偏移量为 15*20*25 = 7500，把j增加7500保证没有负数
f[i][j + hook[k]*weights[i]] += f[i-1][j];
f[G][7500] 为最后结果。
POJ 1276
很裸的多重背包。用二进制思想转化成完全背包和01背包。背包九讲还得翻翻
贴下代码，当三种背包的模板了。
View Code #include#include #include using namespace std; const int N = 100010; int dp[N]; int k[20]; int c[20]; int V, n; void complete_pake(int i) { int j; for(j = c[i]; j <= V; ++j) { dp[j] = max(dp[j], dp[j - c[i]] + c[i]); } } void zero_one_pake(int i) { int m = 1, j; while(k[i]) { if(m > k[i]) m = k[i]; k[i] -= m; for(j = V; j >= m * c[i]; --j) { dp[j] = max(dp[j], dp[j - m * c[i]] + m * c[i]); } m <<= 1; } } int main() { //freopen("data.in", "r", stdin); int i; while(~scanf("%d%d", &V, &n)) { for(i = 0; i < n; ++i) { scanf("%d%d", &k[i], &c[i]); } memset(dp, 0, sizeof(dp)); for(i = 0; i < n; ++i) { if(c[i]*k[i] > V) complete_pake(i); else zero_one_pake(i); } printf("%d\n", dp[V]); } return 0; }
这题做过好几遍了。。妹的！我把W，跟L的位置搞反了。
从尾往头找，dp[i]表示[i, L-1]要删除的元素
View Code #include#include #include #include using namespace std; const int N = 660; const int M = 330; const int inf = ~0u>>2; char str[M]; char word[N][30]; int dp[M]; int W, L; int solve() { int i, j, k, p, l; for(i = 0; i < M; ++i) dp[i] = 0; for(i = L - 1; i >= 0; --i) { dp[i] = dp[i+1] + 1; for(j = 0; j < W; ++j) { if(str[i] == word[j][0]) { l = strlen(word[j]); p = i + 1; k = 1; while(k < l && p < L) { if(str[p] == word[j][k]) ++k; ++p; } if(k == l) { //printf("%d %d %d\n", k, p, p - i - k); dp[i] = min(dp[i], dp[p] + p - i - k); } } } //printf("%d %d\n", i, dp[i]); } return dp[0]; } int main() { //freopen("data.in", "r", stdin); int i; while(~scanf("%d%d", &W, &L)) { scanf("%s", str); for(i = 0; i < W; ++i) { scanf("%s", word[i]); } printf("%d\n", solve()); } return 0; }
题意看错了，wa了一次。意思是从一个value无序的序列中删掉一些数据。使得这个序列的value排列成为如下图所示
思路是正序进行一次LIS。逆序进行一次LIS，然后枚举中值
渣代码
View Code #include#include #include #define clear(x) memset(x, 0, sizeof(x)) #define loop(i, b, n) for(i = b; i < n; ++i) using namespace std; const int N = 1024; const int eps = 1e-8; double num[N]; int dpl[N]; int dpr[N]; int cmp(double x) { if(x > eps) return 1; if(x < -eps) return -1; return 0; } int main() { //freopen("data.in", "r", stdin); int n, i, j, ans, l, r; while(~scanf("%d", &n)) { clear(num); loop(i, 0, n) { scanf("%lf", &num[i]); } //left clear(dpl); dpl[0] = 1; loop(i, 1, n) { ans = dpl[i]; loop(j, 0, i) { if(cmp(num[i] - num[j]) > 0 && ans < dpl[j]) { ans = dpl[j]; } } dpl[i] = ans + 1; } //right clear(dpr); dpr[n - 1] = 1; for(i = n - 2; i >= 0; --i) { ans = dpr[i]; for(j = n - 1; j > i; --j) { if(cmp(num[i] - num[j]) > 0 && ans < dpr[j]) { ans = dpr[j]; } } dpr[i] = ans + 1; //printf("%d\n", dpr[i]); } ans = n; for(i = 0; i < n; ++i) { l = 0; for(j = 0; j <= i; ++j) { l = max(l,dpl[j]); } r = 0; for(j = i + 1; j < n; ++j) { r = max(r, dpr[j]); } l = i + 1 - l; r = n - i - 1 - r; //printf("%d %d\n", l, r); ans = min(ans, l + r); } printf("%d\n", ans); } return 0; }
裸LIS
POJ 3176
看过lrj”蓝书“的都知道，这个dp里讲的第一道例题。。很简单的转移方程。
从下往上推。
dp[i][j] = mp[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
POJ 1159
思路：求(n - 正序和逆序的最长公共子序列)。
二维数组解法：int存不开，我晕晕呼呼的开了char型。结果从昨晚错到现在。char 型的数据范围[-128, 127]。。。这里要用short。。。
滚动数组：dp[2][N]，dp[0][]表示前一种状态。dp[1][]表示现在要求的状态。（memset严重不靠谱！）
View Code #include#include #include using namespace std; const int N = 5010; char s[N]; int dp[2][N]; int main() { //freopen("data.in", "r", stdin); int n, i, j; while(~scanf("%d", &n)) { memset(s, 0, sizeof(s)); scanf("%s", s + 1); for(i = 0; i <= n + 1; ++i) dp[0][i] = dp[1][i] = 0; for(i = 1; i <= n; ++i) { for(j = 1; j <= n; ++j) { if(s[i] == s[n - j + 1]) dp[1][j] = max(dp[0][j - 1] + 1, max(dp[0][j], dp[1][j - 1])); else dp[1][j] = max(dp[0][j], dp[1][j - 1]); } for(j = 1; j <= n; ++j) { dp[0][j] = dp[1][j]; dp[1][j] = 0; } } printf("%d\n", n - dp[0][n]); } return 0; }
POJ 1080
题意是给一个表，一个嘌呤（ 嘧啶） 和另一个嘌呤（嘧啶） 的耦合值。给出两串基因，求其最大的耦合值。
转移方程很明显
f[i][j]表示串s1取到i位置和串s2取到j位置的最大耦合值。
f[i][j] = max{
f[i - 1][j - 1] + mp[s1[i]][s2[j]],
f[i - 1][j] + mp[s2[j]]['-'],
f[i][j - 1] + mp[s1[i]]['-']
}
初始化
f[0][0] = 0;
f[i][0] = f[i - 1][0] + mp[s1[i]]['-'];
f[0][j] = f[0][i - 1] + mp[s2[j]]['-'];
ps:s2串的初始化写错了。wa了一次！-_-!
POJ 1260
刚开始我就没敢写状态方程。后来看到一坨证明后才敢写。
规律1、如果等级为a的pearls可以归并到等级为b的pearls上去，则a必定全部归并到b上。不存在以等级为a的价格购买一部分，再以等级为b的价格购买一部分
规律2、如果等级为a的pearls把比它等级低的pearls归并时必定是连续的。比如从等级k到a，只能是:{a, a-1}, {a, a-1, a-2}...{a, a - 1, ... a - k}这些种情况。
以下部分摘自：
1）证明：假设等级为a的珍珠的一部分以等级为 i 的价格购买，另一部分以等级为 j 的价格购买，且 i 不等于 j ，则由题意 p(i) 不等于 p(j) ，不妨设 i < j ，则 p(i) < p(j) ，那么，如果把以价格为 p(j) 买的那部分珍珠以 价格为 p(i) 买的话，会更省钱。即这不是最省钱的方案，与题意矛盾。 所以假设不成立，此题得证。
2）证明：命题可以等价为如果等级为a的珍珠要与等级为 i 的珍珠合并（a< i ），那么凡是等级介于 a 和 i 之间的珍珠也必须与等级为 i 的珍珠合并。
假设存在等级为 j 的珍珠，满足 a < j < i ，并且它没有与等级为 i 的珍珠合并。那么，
1..如果它没有与任何珍珠合并。因为 p(j) < p(i) ，所以如果等级为 a 的珍珠以 p(j) 的价格购买的话会更省 钱。这与假设矛盾。
2..它与一个等级为 k 的珍珠合并（k 不等于 i )。那么，
1.... 当 j<k<i 时，存在等级为k的珍珠没有与其他珍珠合并，这种情况已经在1..中证明了矛盾。
2.... 当 k>i 时， p(k)>p(i) 这个 j 等级的珍珠以 p(k)的价格买当然不如以 p(i) 的价格买合算。所以这也不是最省钱的方案，与题意矛盾。
有上面两条规律转移方程就很好写了。f[i]表示前i种pearls购买所需要的最小花费。
f[i] = min(f[i], f[k] + (a[k + 1] + a[k + 2] + .. + a[i] + 10)*p[i]);
初始化：
memset(f, inf, sizeof(f));
f[0] = 0; f[1] = (a[1] + 10)*p[1];
ps:把dp搞完了。这里的专题都是一些简单dp，好多题都做过。就当复习了，我发现学dp不能看别人的转移方程怎么写的，而是看别人为什么这么写。lrj的“蓝书”和“黑书”关于dp的部分讲的不错，推荐一看。还有算导，讲的很细。埋头看会书，有时候比多刷两道水题来的高效。。。
