P1941——飞扬的小鸟

第一眼以为是搜索,看了标签,背包,dp,emm....; 状态很好设dp[i][j]//表示过了i个柱子,高度在j的最小的点击次数。那怎么转移呢?我们发现上升的时候一秒内可以点好几下,那我们可以把上升看成完全背包,下降变成01背包; 先做完全背包,再做01背包。 因为每一个时刻都有一个下界和上界,所以我们最好开两个数组up和down分别记录上界和下界; 注意dp初始化和最后统计答案

// 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;
}

发表于 2018-08-27 20:00:48 in 题目