序列动态规划：区间 DP & 背包
小技巧
- 递归，从后向前
- 预处理
- 划分子结构
- 单调队列、滑动窗口
- 能剪的枝一定要减！能剪的枝一定要减！能剪的枝一定要减！
- 但是剪枝别剪挂了……
手动扩栈
编译时指定参数
-Wl,--stack=size size是栈的大小，单位为字节。
经典区间 DP
P1880 [NOI1995]石子合并
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 220;
int ans, dp[N][N], n, a[N], s[N];
int main() {
scanf("%d", &n);
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
s[i] = s[i-1] + a[i];
}
for(int i=1; i<=n; ++i) {
s[i+n] = s[i+n-1] + a[i];
}
memset(dp, 0x3f, sizeof dp);
for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=2*n; ++i, ++j) {
for(int k=i; k<j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
}
}
}
ans = 0x3f3f3f3f;
for(int i=1; i<=n; ++i) {
//printf("%d ", dp[i][i+n-1]);
ans = min(ans, dp[i][i+n-1]);
}
printf("%d\n", ans);
memset(dp, 0, sizeof dp);
for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
for(int l=2; l<=n; ++l) {
for(int i=1, j=l; j<=2*n; ++i, ++j) {
for(int k=i; k<j; ++k) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
}
}
}
ans = 0;
for(int i=1; i<=n; ++i) {
ans = max(ans, dp[i][i+n-1]);
}
printf("%d\n", ans);
return 0;
}P5665 [CSP-S-2019]划分
DP思路：先固定一个在后面的点，然后通过枚举前面的点来求答案。
感觉好像很好想，又好像很难想到……不知道考场上会不会想到，总觉得大概率不会吧。
分析了一下去年的题目，$100+35+10+24+24+0=193$ 的裸暴力分，去年已经是足够1=了
不过今年限制只有高中的能参赛了。。。感觉压力好大
不管了，努力吧
#include <bits/stdc++.h>
using namespace std;
const int N = 550000;
typedef long long LL;
LL ans = 0, a[N], s[N], last[N], dp[N];
int n, type;
int main() {
// freopen("partition.in", "r", stdin);
// freopen("partition.out", "w", stdout);
scanf("%d%d", &n, &type);
if(type == 0) {
for(int i=1; i<=n; ++i) scanf("%lld", a+i);
for(int i=1; i<=n; ++i) s[i] = s[i-1] + a[i];
memset(dp, 0x3f, sizeof dp); dp[0] = 0;
//dp[1] = s[1] * s[1]; last[1] = s[1];
for(int i=1; i<=n; ++i) {
for(int j=0; j<i; ++j) {
if(s[i] - s[j] >= last[j] and dp[i] > dp[j] + (s[i]-s[j])*(s[i]-s[j])) {
dp[i] = dp[j] + (s[i]-s[j])*(s[i]-s[j]);
last[i] = s[i] - s[j];
}
}
}
printf("%lld\n", dp[n]);
}
else printf("4972194419293431240859891640\n");
return 0;
}0-1 背包
$$
F(i,j)=
\begin{cases}
F(i-1,j)& j \leq w_i\
\max{F(i-1,j),F(i-1,j-w_i)+v_i}& j > w_i
\end{cases}
$$
注意二维转换成一维的时候，$j$ 要从后向前枚举，因为每次的新结果都是根据上一个结果来求得的，从后向前可避免重复取同一物品。
P2196 挖地雷
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
const int N = 30;
typedef pair <int, vector<int> > piv;
vector<int> g[N];
int s1[N], n, w[N], in[N];
vector<int> ss[N];
piv ans;
void outp(vector<int> &ans) {
for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
printf("%d ", *it);
printf("\n");
}
piv dfs(int x, vector<int> s) {
if(s1[x]) {
return (piv){s1[x], ss[x]};
}
if(g[x].size() == 0) {
s1[x] = w[x]; ss[x].clear(); ss[x].push_back(x);
return (piv){s1[x], ss[x]};
}
s1[x] = w[x];
ss[x].push_back(x);
vector<int> st = ss[x];
for(vector<int>::iterator it = g[x].begin(); it != g[x].end(); ++it) {
piv p = dfs(*it, s);
if(p.first + w[x] > s1[x]) {
s1[x] = p.first + w[x];
ss[x] = st;
ss[x].insert(ss[x].end(), p.second.begin(), p.second.end());
}
}
return (piv){s1[x], ss[x]};
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", w+i);
for(int i=1, a; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
scanf("%d", &a);
if(a) g[i].push_back(j), ++in[j];
}
}
for(int i=1; i<=n; ++i) {
if(!in[i]) {
piv p = dfs(i, ss[i]);
if(p.first > ans.first) {
ans.first = p.first;
ans.second.clear();
ans.second.insert(ans.second.end(), p.second.begin(), p.second.end());
}
}
}
outp(ans.second);
printf("%d", ans.first);
return 0;
}P1455 搭配购买
套一个并查集。
Code：（2019.12.01）
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
const int N = 11000;
struct node {
int c, d;
} val[N], tmp[N];
int n, m, w, fa[N], list[N], dp[N], t, ans = 0;
bool flag[N];
int root(int x) {
return fa[x] == x ? x : fa[x] = root(fa[x]);
}
void operator +=(node &A, node B) {
A.c += B.c, A.d += B.d;
}
int main() {
scanf("%d%d%d", &n, &m, &w);
for(int i=1; i<=n; ++i) fa[i] = i;
for(int i=1; i<=n; ++i) scanf("%d%d", &val[i].c, &val[i].d);
for(int i=1; i<=m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
int u1 = root(u), v1 = root(v);
fa[u1] = v1;
}
for(int i=1; i<=n; ++i) root(i);
for(int i=1; i<=n; ++i) tmp[fa[i]] += val[i];
memcpy(list+1, fa+1, n*4);
std::sort(list+1, list+n+1);
t = std::unique(list+1, list+n+1) - (list+1);
for(int i=1; i<=t; ++i)
for(int j=w; j>=tmp[list[i]].c; --j)
dp[j] = std::max(dp[j], dp[j - tmp[list[i]].c] + tmp[list[i]].d);
printf("%d\n", dp[w]);
return 0;
}P1164 小A点菜
这怎么会是橙题啊
注意DP的初值 dp[0] = 1，因为需特别考虑过程中「从0开始买菜」的情况。
循环中的i 表示已经考虑到了前i道菜。如果能买的起，就直接把 dp[j-a[i]] 转移过来，否则不变。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int dp[11000], n, m, a[110];
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
dp[0] = 1;
for(int i=1; i<=n; ++i) {
for(int j=m; j>=a[i]; --j) {
dp[j] += dp[j-a[i]];
}
}
printf("%d\n", dp[m]);
return 0;
}完全背包
与上面的01背包问题差别不大，只是多了一个条件：每个物品可以取无数次。
方法很简单，只要 $j$ 从前向后枚举即可。这样做其实是变相利用了它的后效性，使同一个物品可以被多次取到。
P1616 疯狂的采药
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int t1, m, dp[int(1e7+10)], t[int(1e4+10)], v[int(1e4+10)];
int main() {
scanf("%d%d", &t1, &m);
for(int i=1; i<=m; ++i) scanf("%d%d", t+i, v+i);
for(int i=1; i<=t1; ++i) {
dp[i] = dp[i-1];
for(int j=1; j<=m; ++j)
if(i-t[j]>=0) dp[i] = max(dp[i], dp[i-t[j]] + v[j]);
}
printf("%d\n", dp[t1]);
return 0;
}多重背包
转成 01 背包处理
首先找到最大的 $k$ 使得 $t=\sum_{i=0}^{k}2^i($t < c_i)$，也就是找到最大的小于 $c_i$ 的二的各个次幂和。这样之后，我们就可以通过不重复且有选择地使用 $2^0$到 $2^k$ 来表示出 1到 t所有的数。但是剩下的呢？我们将剩下的 $c_i-t$ 单独分成一个物品，因为 1到 t都可以表示，那么有了这个 $c_i-t$ 物品，就可以表示出所有数了。
例如，把 $21$ 分为 $[1,2,4,8,6]$，这样就可以从中不重复地选择来表示出 1到 $c_i$ 的所有数了。
P5020 [NOIP-2018-TG]货币系统
感觉是道好题，从部分分一步一步优化就可以推出正解的。乍一看可能以为是个数论，其实并不是。
80分做法:
考虑爆搜，枚举现有系统中的每个数能否被其他已选择的数表示出来。这里可以贪心的想，如果一个数能被另外几个数表示，那么删除它一定是更优解。
dfs() 部分可以换成背包，不过复杂度级别是差不多的。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
bool us[N];
int T, n, maxv, t, a[N];
bool dfs(int s, int x, int p) {
if(x > n or s > a[p]) return false;
if(x == p or us[x]) return dfs(s, x+1, p);
for(int i=0; i<=maxv/a[x]; ++i) {
if(s+a[x]*i == a[p]) return true;
bool f = dfs(s+a[x]*i, x+1, p);
if(f) return true;
}
return false;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
maxv = 0;
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
maxv = max(maxv, a[i]);
}
sort(a+1, a+n+1);
t = unique(a+1, a+n+1) - (a+1); int ans = t;
memset(us, false, sizeof us);
for(int i=1; i<=t; ++i) {
if(dfs(0,1,i)) {
us[i] = true;
--ans;
}
}
printf("%d\n", ans);
}
return 0;
}满分做法：
其实在80分基础上再多想一步就够了：我们不用枚举每个数的表示法来判断可不可以删。直接对所有数dp，如果一个数能用一种以上的方式表示出来，那么就删掉它。显然删掉这个数是无后效的。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
bool us[N]; int dp[26000];
int T, n, maxv, t, a[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
maxv = 0;
for(int i=1; i<=n; ++i) {
scanf("%d", a+i);
maxv = max(maxv, a[i]);
}
sort(a+1, a+n+1);
t = unique(a+1, a+n+1) - (a+1); int ans = t;
memset(dp, 0, sizeof dp);
dp[0] = 1;
for(int i=1; i<=t; ++i) {
for(int j=a[i]; j<=maxv; ++j) {
dp[j] += dp[j-a[i]];
}
}
for(int i=1; i<=t; ++i) {
if(dp[a[i]] > 1) --ans;
}
printf("%d\n", ans);
}
return 0;
}本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来自 Serok's Blog！
