原题链接

考察:线性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 }