【Luogu】P1941飞扬的小鸟（DP）

我发现现在没了题解我做普及提高+的题也做不了　 更不要说这些提高+难度的‍题

  此题是一个二维DP。暴力是三重循环ijk，k枚举在i位置上的点击次数。即

  for(int i=1;i<=n;++i)

       for(int j=1;j<=m;++j)

           for(int k=1;j-k*up[i]>0;k++)    f[i][j]=min(f[i][j],f[i][k]+k);

  这样的暴力能拿到80分。但是很不幸，我一开始搞错了，所以只拿了60，剩下20是TLE。

  后来发现可以把水管放在外面计算。也就是三重暴力算完之后，把水管部分的值修改为INF，让它被覆盖掉。

  然后有一个想法就是f[i][j]=f[i][j-up[i]]。也就是说现在这个状态(比如点a次)可以从点a-1次的状态转移过来。

  于是100分，但是1829ms被zht大佬完虐(137)

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>

inline long long min(long long a,long long b){    return a<b?a:b;    }

long long INF;
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

struct Point{
    long long up,down;
    Point(){up=100000;down=0;}
}Map[10010],Pipe[10010];

long long f[10010][1010];
long long ans;
long long tot;
int main(){
    long long n=read(),m=read(),K=read();
    for(long long i=0;i<n;++i){
        Map[i].up=read();
        Map[i].down=read();
    }
    for(long long i=1;i<=K;++i){
        long long pos=read();
        Pipe[pos].down=read();
        Pipe[pos].up=read();
    }
    memset(f,127/3,sizeof(f));
    ans=INF=f[0][0];
    for(long long i=0;i<=m;++i)   f[0][i]=0;
    for(long long i=1;i<=n;++i){
        for(long long j=1;j<=m;++j){
            if(j>Map[i-1].up){
                f[i][j]=min(f[i][j],f[i-1][j-Map[i-1].up]+1);
                f[i][j]=min(f[i][j],f[i][j-Map[i-1].up]+1);
            }
            if(j==m)
                for(long long k=j-Map[i-1].up;k<=m;++k){
                    f[i][j]=min(f[i][j],f[i-1][k]+1);
                    f[i][j]=min(f[i][j],f[i][k]+1);
                }
        }
        for(long long j=1;j<=m;++j)
            if(f[i][j]>f[i-1][j+Map[i-1].down]&&j+Map[i-1].down<=m)
                    f[i][j]=f[i-1][j+Map[i-1].down];
        long long minn=INF;
        for(long long k=1;k<=m;++k){
            if(k<=Pipe[i].down)    f[i][k]=INF;
            if(k>=Pipe[i].up)    f[i][k]=INF;
            if(minn>f[i][k])    minn=f[i][k];
        }
        if(minn==INF){
            printf("0
%lld",tot);
            return 0;
        }
        if(Pipe[i].up<=m)    tot++;
    }
    
    for(long long i=1;i<=m;++i){
        if(ans>f[n][i]) ans=f[n][i];
    }
    printf("1
%lld",ans);
    return 0;
}