题解 P1941 【飞扬的小鸟 】

[题目传送门](https://www.luogu.org/problem/P1941) ~~我用了瞎想出来的单调队列优化DP，A掉后一看题解才发现就是一个完全背包~~。 令$F_{i,j}$表示到达$(i,j)$所用的最少的点击数，那么$f_{i,j}$要么是从$f_{i-1,j+y}$转移过来，要么是从$f_{i-1,j-k*x}$转移过来（k表示点击屏幕数），~~似乎这样还可以用滚动数组~~。推出转移方程$f_{i,j}=\min(f_{i-1,i+y},f_{i-1,j-k*x}+k)$，如果这个点到达不了，就不需要转移了。 ~~然后我们发现这样复杂度是$O(NM^2)$的，过不了~~，于是考虑用单调队列优化成$O(NM)$的。 第一种转移直接转移掉就好了，关键在于第二种转移怎么找之前的最小值。 如果你学过单调队列优化多重背包，会发现这和单调队列优化多重背包挺像的，没学过也没关系。 因为小鸟只能从$(i-1,j-k*x)$跳到$(i,j)$，因此我们可以把每个节点的纵坐标按照%x的余数分成x组，这样组与组之间就互不影响了。 接着考虑组内部的状态转移，显然对于$F_{i,j}$只有$\min(f_{i-1,j-k*x}+k)$会对答案有贡献，因此我们只需要维护$f_{i-1,j-k*x}+k$的最小值，只需要用一个单调队列就行了。 最后注意一个坑点：小鸟最高只能跳到横坐标为m，所以要把$f_{i,m}$处理一下。 代码： ``` cpp #include<bits/stdc++.h> #define inf 1000000000 inline int min(const int &a,const int &b){return a<b?a:b;} inline int read(){int x=0;char c=getchar();while(c<'0' || c>'9')c=getchar();while(c>='0' && c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();return x;}//快读 inline int quzheng(int a,int b){if(a==0)return 1;return (a%b==0)?(a/b):(a/b+1);}//顾名思义，取整 int n,m,k,x[10001],y[10001],f[10001][1001],q[1001],l,r,ans; bool b[10001][1001],g[10001];//b数组表示(i,j)是否有管子，g数组表示第i列是否有管子 int main() { n=read(),m=read(),k=read(); for(register int i=1;i<=n;i++){x[i]=read(),y[i]=read();for(register int j=1;j<=m;j++)f[i][j]=inf;}//初始化为正无穷 for(register int i=1,p,l,h;i<=k;i++){p=read(),l=read(),h=read();for(register int j=0;j<=l;j++)b[p][j]=1;for(register int j=h;j<=m;j++)b[p][j]=1;g[p]=1;}/ for(register int i=1;i<=n;i++) { if(g[i-1])ans++;//统计已经跳过的管子数 for(register int j=1;j<=m-y[i];j++)if(!b[i][j])f[i][j]=f[i-1][j+y[i]];//状态转移 if(!b[i][m] && x[i])for(register int j=1;j<=m;j++)if(!b[i-1][j])f[i][m]=min(f[i][m],f[i-1][j]+quzheng(m-j,x[i]));//提前处理一下f[i,m] for(register int j=0;j<x[i];j++)//处理每一组 { l=1,r=0;//清空单调队列 int maxp=(m-j)/x[i];//最多能点击多少次 for(register int k=0;k<=maxp;k++) { if(k*x[i]+j==0)continue;//横坐标为0的不能转移 if(l<=r && !b[i][k*x[i]+j])f[i][k*x[i]+j]=min(f[i][k*x[i]+j],f[i-1][q[l]*x[i]+j]+k-q[l]);//转移 if(f[i-1][k*x[i]+j]==inf)continue;//如果(i-1,k*x+j)无法到达就跳过 while(l<=r && f[i-1][q[r]*x[i]+j]+k-q[r]>=f[i-1][k*x[i]+j])--r;//单调队列维护最小值 q[++r]=k;//推入队尾 } } bool bb=0;//检测是否有跳过该管子 for(register int j=1;j<=m;j++)if(f[i][j]!=inf){bb=1;continue;} if(!bb){printf("0\n%d",ans);return 0;}//没跳过就直接退出 } printf("1\n"); ans=inf; for(register int i=1;i<=m;i++)ans=min(ans,f[n][i]); printf("%d",ans); } ```