洛谷P1941-飞扬的小鸟
知识点
dp（背包，但是要自己建模），分类讨论（很多细节!!!）
思路
- 状态：dp[i][j]表示走到横坐标为i、纵坐标为j时的最少点击屏幕数。
- 状态转移：从1到n枚举 i ，再分情况枚举不同范围的 j ；
1）下降来：dp[i-1][j+y[i]]；
2）上升来，可以上升很多次：dp[i-1][j-t*x[i]]+t；
3）下降可看作01背包，上升可看作完全背包。 - 初始化：dp[ 0 ][ 1 ]~dp[ 0 ][ m ]为0，其余为inf
- 特判：
1）小鸟高度为m时：dp[ i ][ m ] = min( dp[ i ][ m ]~dp[ i ][ m+x[ i ] ] )； 2）
2）管道：用flag[ i ][ j ]记录(i , j)是否属于管道，是为1，否为0；再用f[ i ]记录第 i 列是否有管道，便于无法到达终点时输出通过的管道数量。
注意
- 题意理解：
1）小鸟高度为m时不会失败，只是不会再上升了；
2）管道：有管道的列，管道中间部分才是可以走的（不包括上下边沿）；没管道的列，出了高度为0的都是可以走的； - 逻辑：
考虑如下情况：向上跳两步，其中第一步会撞在管道上，但第二步不会；
这种情况是可以跳两步的，但在错误代码中会被continue掉；解决办法是不要一遇到管道就continue，而是最后再把属于管道的位置的dp数组设为inf。
错误代码：
- 空间：因为可能飞出去，dp数组第二维的上限是m+x[ i ]，所以空间要开M*2。
- 细节：24行中，若dp[ i-1 ][ j-x[ i ] ]和dp[ i ][ j-x[ i ] ]都是inf，则dp[ i ][ j ]可能为inf+1，故36行的判断应是 if( dp[ i ][ j ]!=inf && dp[ i ][ j ]!=inf+1 )。
完整代码
#include<iostream>
#define inf 1e9
#define N 10005
#define M 1005
using namespace std;
int n, m, k, x[N], y[N], dp[N][M*2];
bool flag[N][M*2], f[N];
int main() {
cin>>n>>m>>k;
for(int i=1;i<=n;i++) scanf("%d%d", &x[i], &y[i]);
for(int i=1;i<=k;i++) { //管道
int p, l, h;
scanf("%d%d%d", &p, &l, &h); //横坐标，下边，上边
f[p]=1; //记录第i列是否有管道
for(int j=0;j<=l;j++) flag[p][j]=1;
for(int j=h;j<=m;j++) flag[p][j]=1; //flag=1不能走，flag=0可以走
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j]=inf;
for(int i=1;i<=m;i++) dp[0][i]=0;
for(int i=1;i<=n;i++) {
for(int j=x[i]+1;j<=m+x[i];j++) //上升
dp[i][j]=min(dp[i-1][j-x[i]]+1, dp[i][j-x[i]]+1);
for(int j=m+1;j<=m+x[i];j++) //特判j==m时
dp[i][m]=min(dp[i][m], dp[i][j]);
for(int j=1;j<=m-y[i];j++) //下降
dp[i][j]=min(dp[i][j], dp[i-1][j+y[i]]);
for(int j=1;j<=m;j++)
if(flag[i][j]) dp[i][j]=inf;
}
int cnt=0;
for(int i=1;i<=n;i++) {
bool ok=0;
for(int j=1;j<=m;j++)
if(dp[i][j]!=inf && dp[i][j]!=inf+1) {
ok=1; break;
}
if(!ok) {
printf("0\n%d", cnt);
return 0;
}
else cnt+=f[i];
}
int ans=inf;
for(int i=1;i<=m;i++) ans=min(ans, dp[n][i]);
printf("1\n%d", ans);
return 0;
}
