P1941——飞扬的小鸟
wangyitong
2018-08-27 20:00:48
第一眼以为是搜索，看了标签，背包，dp，emm....；
状态很好设dp[i][j]//表示过了i个柱子，高度在j的最小的点击次数。那怎么转移呢？我们发现上升的时候一秒内可以点好几下，那我们可以把上升看成完全背包，下降变成01背包；
先做完全背包，再做01背包。
因为每一个时刻都有一个下界和上界，所以我们最好开两个数组up和down分别记录上界和下界；
注意dp初始化和最后统计答案
```cpp
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define max maxx
#define min minn
using namespace std;
template <class T> void in(T &x) {
x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if (f) x = -x;
}
inline int maxx(int x,int y) {
return x>y?x:y;
}
inline int minn(int x,int y) {
return x<y?x:y;
}
inline int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
int dp[10050][1200];//飞过i个柱子，高度为j的最小点击次数；
int up[12000],down[12000];//第i个位置可过的上界和下界 ;
int fly[12000],drop[12000];//第i个位置点击一次可上升的高度和不点击的下降高度
int n,m,k,id,l,h,endd,tot;
bool tract[12000];
int main() {
memset(dp,0x3f,sizeof dp);
in(n),in(m),in(k);
for(ri i=0; i<n; ++i) {
in(fly[i]),in(drop[i]);
up[i]=m;
down[i]=1;
}
for(ri i=1; i<=m; ++i)
dp[0][i]=0;//初始化,因为他说在哪个高度开始都可以。
for(ri i=1; i<=k; ++i) {
in(id),in(l),in(h);
up[id]=h-1;
down[id]=l+1;
tract[id]=true;
}
for(ri i=0; i<n; ++i)
for(ri j=up[i]; j>=down[i]; --j)
if(dp[i][j]!=0x3f3f3f3f) {
endd=i;//记录最远能飞到哪，用于统计没能到终点时，经过的柱子数。
int cnt=(m-j)/fly[i]+1;
dp[i+1][j-drop[i]]=min(dp[i+1][j-drop[i]],dp[i][j]);//我们为什么要用 dp[i][j]更新dp[i+1][j-drop[i]呢，因为我们是往后推得，要用前面求过的状态，更新当前状态
for(ri tt=1; tt<=cnt; ++tt) {
if(dp[i+1][min(m,j+fly[i]*tt)]>dp[i][j]+tt)
dp[i+1][min(m,j+fly[i]*tt)]=dp[i][j]+tt;
else
break;//这句话一定得有，能剪掉好多。
}
}
int minm=233333333;
for(int i=1; i<=m; ++i)
minm=min(minm,dp[n][i]);
if(minm==233333333) {
for(ri i=0; i<=endd; ++i)
if(tract[i])
tot++;
printf("0\n%d",tot);
} else
printf("1\n%d",minm);
return 0;
}
```