【洛谷P1941】飞扬的小鸟

时间：2021-09-03 03:26:54

f [ i ] [ j ] 表示横坐标为 i ，高度为 j 时的最小点击次数

分别dp处理：

1.上升，（1）<m

（2）>=m

2.下降

3.管道

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N=,M=;

 const int INF=;

 int n,m,k,f[N][M],up[N],down[N],l[N],h[N],flag[N];

 int min(int x,int y){

     return x<y?x:y;

 }

 void print(int x){

     int sum=;

     for (int i=;i<x;i++)

         if (flag[i])

             sum++;

     printf("0\n%d",sum);

 }

 int main(){

     int x,y,p;

     scanf("%d %d %d",&n,&m,&k);

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

         scanf("%d %d",&x,&y);

         up[i]=x;

         down[i]=y;

     }

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

         h[i]=m+;

         l[i]=;

         flag[i]=;

     }

     for (int i=;i<=k;i++){

         scanf("%d %d %d",&p,&x,&y);

         h[p]=y;

         l[p]=x;

         flag[p]=;

     }

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

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

             f[i][j]=INF;

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

         f[][j]=;

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

         for (int j=up[i]+;j<=m;j++){

                 f[i][j]=min(f[i][j],min(f[i][j-up[i]],f[i-][j-up[i]])+);

         }//up<m

         for (int j=m-up[i];j<=m;j++)

             f[i][m]=min(f[i][m],min(f[i-][j],f[i][j])+);//^up>=m

         for (int j=;j<=m-down[i];j++)

             f[i][j]=min(f[i][j],f[i-][j+down[i]]);//down

         for (int j=h[i];j<=m;j++)//shangjie

             f[i][j]=INF;

         for (int j=;j<=l[i];j++)//xiajie

             f[i][j]=INF;

         int judge=;

         for (int j=;j<=m;j++)//check

             if (f[i][j]<INF)

                 judge=;

         if (!judge){

             print(i);

             return ;

         }

     }

     int ans=INF;

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

         ans=min(ans,f[n][j]);

     printf("1\n%d",ans);

     return ;

 }

STD

相关文章