考察:线性dp+背包dp
思路:
每个横坐标可以选择按或者不按,这种组合问题求最优解可以考虑背包dp.
易知f[i][j]为以i为横坐标,j为纵坐标的最小按键次数.这道题不需要不通过后判两次dp.只需要在当前坐标存在管道后检测是否通过管道,如果不通过就是输出0 当前管道数-1.那么dp转移就是f[i][j] = min(f[i-1][j+y],f[i-1][j-k*x]+k).前面的是01背包,后面的是完全背包,根据完全背包的优化可以用f[i][j-x]+1代替k的循环枚举.
还有要注意的是高度最多到m的情况.也就是说当j+k*x>m,dp方程为f[i][min(j+k*x,m)] = f[i-1][j]+k.所以跳得比m高的情况不能直接判违法.
关于初始化: 首先将f数组全部变为0x3f,但f[0][1~m] = 0.
空间优化:因为只用到了i-1和i所以可以滚动数组.注意每次滚动的时候要将f[i][0~m+x]全部变为INF,这是模拟未滚动的f数组.
1 #include <iostream>
2 #include <cstring>
3 #include <map>
4 using namespace std;
5 const int N = 10010,M =2010;
6 const int INF = 0x3f3f3f3f;
7 typedef pair<int,int> PII;
8 int n,m,k,f[2][M];
9 PII p[N];
10 map<int,PII> mp;
11 void solve()
12 {
13 memset(f,0x3f,sizeof f);
14 int cnt = 0;
15 for(int i=1;i<=m;i++) f[0&1][i] = 0;
16 for(int i=1;i<=n;i++)
17 {
18 int x = p[i].first,y=p[i].second;
19 for(int j=0;j<=m+x;j++) f[i&1][j] = INF;
20 for(int j=1+x;j<=m+x;j++)//按多次
21 f[i&1][j] = min(f[i-1&1][j-x]+1,f[i&1][j-x]+1);
22 for(int j=1+m;j<=m+x;j++)//顶天
23 f[i&1][m] = min(f[i&1][j],f[i&1][m]);
24 for(int j=1;j+y<=m;j++)//不按
25 f[i&1][j] = min(f[i&1][j],f[i-1&1][j+y]);
26 if(!mp.count(i)) continue;
27 int st = mp[i].first,ed = mp[i].second,ans = INF;
28 for(int j=0;j<=st;j++)
29 f[i&1][j] = INF;
30 for(int j=ed;j<=m;j++)
31 f[i&1][j] = INF;
32 for(int j=st+1;j<ed;j++)
33 ans = min(f[i&1][j],ans);
34 if(ans>=INF) {printf("0\n%d\n",cnt);return;}
35 else cnt++;
36 }
37 int ans = INF;
38 for(int i=1;i<=m;i++) ans = min(ans,f[n&1][i]);
39 printf("1\n%d\n",ans);
40 }
41 int main()
42 {
43 scanf("%d%d%d",&n,&m,&k);
44 for(int i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
45 for(int i=1;i<=n;i++)
46 {
47 int x,l,r;
48 scanf("%d%d%d",&x,&l,&r);
49 mp[x] = {l,r};
50 }
51 solve();
52 return 0;
53 }