NOIP 提高组 2014 飞扬的小鸟(记录结果再利用的DP)

时间：2024-01-18 15:02:08

传送门

https://www.cnblogs.com/violet-acmer/p/9937201.html

参考资料：

　　[1]:https://www.luogu.org/blog/xxzh2425/fei-yang-di-xiao-niao-ti-xie-p1941-post

　　[2]:https://www.luogu.org/blog/JOE/solution-p1941

需注意的地方：

　　(1):在每一时刻都可以点击屏幕好多好多次，就算是在m高度处也可以点击屏幕使其保持在最高点。

题解：

　　相关变量解释：

 int n,m,k;

 int x[maxn];//x[i] : 在X=i处点击屏幕，在i+1处上升x[i]高度

 int y[maxn];//y[i] : 在X=i处不点击屏幕，在i+1处下降y[i]高度

 struct Node

 {

     int id;//水管的编号

     int l,h;//l : 下边界； h : 下边界

     Node(int a=,int b=,int c=):id(a),l(b),h(c){}

 }pipeline[maxn];//水管信息

 int dp[maxn][*];//dp[i][j] : 来到i处的j高度所需的最少的点击量，至于为什么列要开2*1000，一会解释

　　根据dp定义，很容易写出状态转移方程：

 dp[i][j]=min(dp[i][j],dp[i-1][j-k*x[i-1]]+k);
 dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]);

　　1是指从(i-1,j-k*x[i-1])处点击屏幕k次来到(i,j)处

　　2是指从(i-1,j+y[i-1])处不点击屏幕来到(i,j)处，最终答案就是1,2中最小的那个

　　如果将此状态写出的代码提交上去，会超时的，为什么呢？

　　因为每个点(i,j)都需要循环 k 次来找出最小点击量，这就是O(Σni=1Σmj=1kj)的复杂度，而O(Σni=1Σmj=1kj)最大为O(n*m2)。

　　那要怎么办呢？注意观察一下：

　　假设来到(i,10)处，x[i-1]=3

NOIP 提高组 2014 飞扬的小鸟(记录结果再利用的DP)

　　在计算dp[ i ][10]的时候，dp[ i-1][4],dp[ i-1][1]相对大小已经在计算dp[i][7]的时候计算过了，所以应利用好之前的结果，那么状态转移方程就变为：

 dp[i][j]=min(dp[i-1][j-x[i-1]]+1,dp[i][j-x[i-1]]+1);
 dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]);

　　下面来证明一下正确性：

　　如果dp[i][7]=dp[i-1][4] => dp[i-1][4]+1 < dp[i-1][1]+2;

　　方程两端同时加上1 => dp[i-1][4]+2 < dp[i-1][1]+3,那来到 j = 10时，dp[i-1][4]+2与dp[i-1][1]+3的相对大小已经在求解dp[i][7]的时候求解出来了。

　　根据上述转移方程得到：

 void updataDp(int i,int a,int b)

 {

     for(int j=+x[i-];j <= m+x[i-];++j)//从(i-1,j-x[i-1])处点击屏幕来到(i,j)处

         dp[i][j]=min(dp[i-][j-x[i-]]+,dp[i][j-x[i-]]+);

     for(int j=;j < m;++j)//特判(i,m)点

     {

         int tot=(m-j)/x[i-];

         while(j+tot*x[i-] < m)

             tot++;

         dp[i][m]=min(dp[i][m],dp[i-][j]+tot);

     }

     for(int j=;j+y[i-] <= m;++j)//从(i-1,j+y[i-1])处不点击屏幕来到(i,j)处

         dp[i][j]=min(dp[i][j],dp[i-][j+y[i-]]);

     dp[i][m]=min(dp[i][m],dp[i-][m]+);//就算在i-1处到达m点，也可以通过点击一次屏幕来到(i,m)处

     for(int j=;j < a;++j)//[a,b]是i处无管道的区域，[a,b]之外都不可达，所以赋值为INF

         dp[i][j]=INF;

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

         dp[i][j]=INF;

 }

　　其中(i,m)点的特判可改为

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

     dp[i][m]=min(dp[i][m],dp[i][j]);

　　这是为什么第一个for( )的范围最大到 m+x[i-1]，以及dp[][]的列开到2*1000的原因；

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define mem(a,b) memset(a,b,sizeof(a))

 const int maxn=1e4+;

 int n,m,k;

 int x[maxn];//x[i] : 在X=i处点击屏幕，在i+1处上升x[i]高度

 int y[maxn];//y[i] : 在X=i处不点击屏幕，在i+1处下降y[i]高度

 struct Node

 {

     int id;//水管的编号

     int l,h;//l : 下边界； h : 下边界

     Node(int a=,int b=,int c=):id(a),l(b),h(c){}

 }pipeline[maxn];//水管信息

 int dp[maxn][*];//dp[i][j] : 来到i处的j高度所需的最少的点击量，至于为什么列要开2*1000，一会解释

 bool cmp(Node _a,Node _b){

     return _a.id < _b.id;//按照管道编号升序排列

 }

 void Updata(int &a,int &b,int &ki,int i)//更新 X=i 处的上下边界

 {

     if(ki <= k && pipeline[ki].id == i)

         a=pipeline[ki].l+,b=pipeline[ki].h-,ki++;

 }

 void updataDp(int i,int a,int b)

 {

     for(int j=+x[i-];j <= m+x[i-];++j)//从(i-1,j-x[i-1])处点击屏幕来到(i,j)处

         dp[i][j]=min(dp[i-][j-x[i-]]+,dp[i][j-x[i-]]+);

     for(int j=;j < m;++j)//特判(i,m)点

     {

         int tot=(m-j)/x[i-];

         while(j+tot*x[i-] < m)

             tot++;

         dp[i][m]=min(dp[i][m],dp[i-][j]+tot);

     }

     for(int j=;j+y[i-] <= m;++j)//从(i-1,j+y[i-1])处不点击屏幕来到(i,j)处

         dp[i][j]=min(dp[i][j],dp[i-][j+y[i-]]);

     dp[i][m]=min(dp[i][m],dp[i-][m]+);//就算在i-1处到达m点，也可以通过点击一次屏幕来到(i,m)处

     for(int j=;j < a;++j)//[a,b]是i处无管道的区域，[a,b]之外都不可达，所以赋值为INF

         dp[i][j]=INF;

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

         dp[i][j]=INF;

 }

 int Check()

 {

     int res=dp[][];

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

         res=min(dp[n][i],res);

     return res;

 }

 int maxPass()

 {

     for(int ki=k;ki >= ;--ki)

         for(int i=pipeline[ki].l+;i < pipeline[ki].h;++i)

             if(dp[pipeline[ki].id][i] < INF)//为什么用 < 而不是用 != 呢？

                 return ki;

     return ;

 }

 void Solve()

 {

     sort(pipeline+,pipeline+k+,cmp);

     mem(dp,INF);

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

         dp[][i]=;

     int ki=;

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

     {

         int a=,b=m;

         Updata(a,b,ki,i);//更新i处的无管道范围[a,b]

         updataDp(i,a,b);

     }

     int res=Check();

     if(res < INF)//为什么用 < 而不是用 != 呢？

         printf("%d\n%d\n",,res);

     else

         printf("%d\n%d\n",,maxPass());

 }

 int main()

 {

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

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

         scanf("%d%d",x+i,y+i);

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

     {

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         pipeline[i]=Node(a,b,c);

     }

     Solve();

 }

　　对代码中的问题解释一下，这是我下午踩的一个坑：

　　看updataDp中的第一个for()

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

     dp[i][j]=min(dp[i-][j-x[i-]]+,dp[i][j-x[i-]]+);

　　如果dp[i-1][j-x[i-1]] == INF 且 dp[i][j-x[i-1]] == INF，那dp[ i ][ j ] == INF+1 > INF;。

　　还发现一个有趣的地方：

　　mem(dp,0x3f) <=> mem(dp,0x3f3f3f3f)

　　但是 0x3f < 0x3f3f3f3f

相关文章