2024年3月7日发(作者：)
noip2013day1T3飞扬的小鸟
（评测平台：洛谷p1941）
题目不讲了，大家都知道。
很显然的一个bfs，实则不然（实则我不会），那么就dp吧，但是怎么优化呢……
心路过程：
暴力
没错，最朴素的暴力背包！
对于ans[i][j]，下降由ans[i-1][j+y[i-1]]转移而来（如果ans[i-1][j+y[i-1]]可到达）；
上升则要玄学操作（详见代码），高度达到m后无法再上升也是一个坑。
变量：
#include
usingnamespacestd;
constint MAXX=1000000;
struct obstacle
{
intp,l,h;//同题面
}o[10010];//存储管道
intn,m,k;
int x[10010]={0},y[10010]={0};//上升和下降
intans[10010][1010]={0},f[10010][1010]={0},sum[10010]={};//f表示这个点是否可飞到
预处理（f[i][j]==-1则[i][j]为水管。f[i][j]==1表示[i][j]可达）：
//忽略读入&读入优化&mycmp
inlinevoid first(){
sort(o+1,o+k+1,mycmp);//按位置排序
for(inti=0;i<=n;++i)
for(int j=0;j<=m;++j)ans[i][j]=MAXX
for(inti=0;i<=m;++i){
f[0][i]=1;
ans[0][i]=0;
}
for(inti=1;i<=k;++i){
sum[o[i].p]=i;//记录到第i列有多少水管
for(int j=0;j<=o[i].l;++j)f[o[i].p][j]=-1;
for(int j=o[i].h;j<=m;++j)f[o[i].p][j]=-1;
}
return;
}
dp：
inlinevoiddp(){
for(inti=1;i<=n;++i){
bool flag=false;//记录当前所在列能否飞过
for(int j=1;j if(f[i][j]<0)continue;//如果当前点是管道直接continue if(f[i-1][j+y[i-1]]>0){//从可到达的点转移，下降处理 f[i][j]=1;//记录当前点可到达 ans[i][j]=min(ans[i][j],ans[i-1][j+y[i-1]]); flag=true; } for(int k=1;k*x[i-1]<=j;++k)//上升 if(f[i-1][j-k*x[i-1]]>0){ f[i][j]=1; s[i][j]=min(ans[i][j],ans[i-1][j-k*x[i-1]]+k); flag=true; } } if(f[i][m]>=0) for(int k=0;k<=m;++k)//顶部处理 if(f[i-1][k]>0){//不用看了，意会就好 f[i][m]=1;int temp; if((m-k)%x[i-1]==0)temp=ans[i-1][k]+(m-k)/x[i-1]; else temp=ans[i-1][k]+(m-k)/x[i-1]+1; if(k==m)temp=ans[i-1][k]+1; ans[i][m]=min(ans[i][m],temp); flag=true; } if(flag==false)print(i-1); } print(n); return; } 输出： inlinevoid print(int place){ if(place printf("0n"); for(inti=place;i>=0;i--) if(sum[i]){//自行体会 printf("%d",sum[i]); exit(0); } printf("0"); exit(0); } intminn=MAXX; for(inti=1;i<=m;i++) if(f[n][i]==1)minn=min(ans,ans[n][i]); printf("1n%d",minn); return; } 光荣TLE 优化 终于，我意识到了，向上飞作为一个完全背包，ans[i][j]可以由ans[i][j-x[i-1]]+1转移而来，但是这样的话，暴力方案中的标记就会出问题： 对于这张图片，假设x[i]=1，那么如果第i+1列有水管的点不去搜索，第i+1列就飞不到了……但是实际上可以点四次来飞到。那么处理方法就是对于当前一列，无论是否有水管都搜索，而要从前一列转移而来时，只从非水管的点转移。 其他部分和暴力一样，不写了。 dp： voiddp(){ for(inti=1;i<=n;++i){ bool flag=false; for(int j=x[i-1];j<=m;++j){ if(f[i-1][j-x[i-1]]!=-1)//从上一行转移 ans[i][j]=min(ans[i][j],ans[i-1][j-x[i-1]]+1); ans[i][j]=min(ans[i][j],ans[i][j-x[i-1]]+1);//完全背包 } for(int j=0;j if(f[i-1][m-j]!=-1) ans[i][m]=min(ans[i][m],ans[i-1][m-j]+1); ans[i][m]=min(ans[i][m],ans[i][m-j]+1); } for(int j=1;j<=m-y[i-1];++j)//下降 if(f[i-1][j+y[i-1]]!=-1) ans[i][j]=min(ans[i][j],ans[i-1][j+y[i-1]]); for(int j=1;j<=m;++j)//判断当前列是否可达 if(f[i][j]!=-1&&ans[i][j]!=MAXX) flag=true; if(!flag)print(i); } print(n+1); return; } 然后就啦。 那么这道纠缠我无数天的题，就，过啦。
发布评论