NOIP2014 Day1 T3(背包DP)

题目是一个无限背包+01背包,但是要先做无限背包,再做01背包。如果先做01背包,那么在做无限背包的时候会出现多次下降的情况。
根据题目,很容易想出设$f[i][j]$为在$x=i, h=j$时的最小点击次数,那么有下列方程(无限背包部分, 即上升部分)
$$f[i][j] = min(f[i][j], f[i-1][j-kx]+1)$$
很明显,这样的做法TLE。
我们回想无限背包的式子,$f[v] = max(f[v], f[v-w[i]]+c[i])$对吧?应该大部分人都记得这个“滚动后的式子”,而原式都不记得了,原式为设$f[i][v]$为前$i$个物品装进$v$容量的最大利益。则状态转移方程为
$$f[i][v] = max(f[i-1][v], f[i][v-w[i]]+c[i])$$
这个方程是”继承$f[i-1]$的值“或者”在$f[i]$中已经计算过的值再用来转移(即实现了多重)”,我们的原方程是不是也可以这样呢?答案是肯定的。
原方程可化为
$$f[i][j] = min(f[i][j-x]+1, f[i][j-x]+1)$$
这样就不会超时了,处理之后的01背包,直接在多重处理完后扫一遍,$f[i][j] = min(f[i][j], f[i-1][j+y])$就能算出来了。
注意此题要因为上升高度大于$m$则为$m$,需要进行特殊判定,并且每个是管道的状态也要转移,因为这个对多重做出了贡献,在处理完之后再进行覆盖最大值即可,否则这里会丢掉25分。直接沦为暴力选手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 10000 + 5, MAXM = 1000 + 5, INF = 1000000000;
int n, m, k, f[MAXN][MAXM], d[MAXN], u[MAXN], l[MAXN], h[MAXN];
void clean() {
for (int i=0;i<=n;i++) {
l[i] = -1;
h[i] = m + 1;
f[i][0] = INF + 1;
for (int j=1;j<=m;j++) {
if (i==0) f[i][j] = 0; else f[i][j] = INF;
}
}
}
void init() {
clean();
for (int i=1;i<=n;i++) {
scanf("%d%d", &u[i], &d[i]);
}
for (int i=1;i<=k;i++) {
int p, x, y;
scanf("%d%d%d", &p, &x, &y);
l[p] = x, h[p] = y;
}
}
void solve() {
int zz = 0, ans = INF;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (j-u[i]>0) {
f[i][j] = min(f[i][j], f[i][j-u[i]]+1);
f[i][j] = min(f[i][j], f[i-1][j-u[i]]+1);
}
if (j==m) {
for (int o=0;o<u[i];o++) {
f[i][j] = min(f[i][j], f[i][m-o]+1);
f[i][j] = min(f[i][j], f[i-1][m-o]+1);
}
}
}
for (int j=1;j<=m;j++) {
if (j+d[i]<=m) f[i][j] = min(f[i][j], f[i-1][j+d[i]]);
}
for (int j=1;j<=l[i];j++) f[i][j] = INF;
for (int j=h[i];j<=m;j++) f[i][j] = INF;
}
for (int i=1;i<=n;i++) {
int ap = INF, flag = 0;
for (int j=1;j<=m;j++) {
if (f[i][j]<INF) flag = 1;
ap = min(ap, f[i][j]);
}
if (!flag) {printf("0\n%d\n", zz); return ;} else ans = ap;
if (l[i]!=-1) zz++;
}
printf("1\n%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d", &n ,&m, &k)==3) init(), solve();
return 0;
}

------ 本文结束 ------