【题解】洛谷P1941 [NOIP2014TG] 飞扬的小鸟（背包DP）

次元传送门：洛谷P1941

思路

从题意可知 在每个单位时间内 可以无限地向上飞 但是只能向下掉一次

所以我们可以考虑运用背包解决这道题

上升时 用完全背包

下降时 用01背包

设f[x][y]为在坐标(x,y)时的最小点击屏幕次数

当飞到天花板时和撞到柱子时特判

一开始设ans为极大值

如果最后一排的值都为极大值则无解

如果无解就倒着回来判断最远能到达第几根柱子

代码

#include<iostream> #include<cstring> using namespace std; #define maxn 10010 int up[maxn],down[maxn],low[maxn],high[maxn]; int f[maxn][2010]; bool vis[maxn]; int n,m,k,cnt,ans; int main() { memset(f,0x3f,sizeof(f));//初始化为极大值 cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>up[i]>>down[i]; for(int i=1;i<=n;i++)//初始化柱子 { low[i]=1; high[i]=m; } for(int i=1;i<=k;i++) { int x,y,z; cin>>x>>y>>z; vis[x]=1; low[x]=y+1; high[x]=z-1; } for(int i=1;i<=m;i++) f[0][i]=0;//第一排全是0 for(int i=1;i<=n;i++)//枚举x坐标 { for(int j=1+up[i];j<=m+up[i];j++)//完全背包 当前点可以由前一个点上升一次而来 f[i][j]=min(f[i-1][j-up[i]]+1,f[i][j-up[i]]+1);//也可以由当前点上升一次而来 for(int j=m+1;j<=m+up[i];j++)//天花板特判 f[i][m]=min(f[i][m],f[i][j]); for(int j=1;j<=m-down[i];j++)//01背包 当前点由前一个点掉下来 f[i][j]=min(f[i][j],f[i-1][j+down[i]]); for(int j=1;j<low[i];j++)//判断柱子 f[i][j]=f[0][0]; //赋值为极大值 for(int j=high[i]+1;j<=m;j++) f[i][j]=f[0][0]; } ans=f[0][0];//赋值为极大值 for(int i=1;i<=m;i++) ans=min(ans,f[n][i]);//查询ans if(ans<f[0][0]) cout<<1<<endl<<ans;//如果有ans else//如果无解 { int now,j; for(now=n;now>=1;now--)//倒着判断 { for(j=1;j<=m;j++)//如果当前排可以到达就退出 if(f[now][j]<f[0][0]) break; if(j<m) break; } ans=0; for(int i=1;i<=now;i++) if(vis[i]) ans++;//计算可以到达的x坐标中有几个管子 cout<<0<<endl<<ans; } }

 

转载于:https://www.cnblogs.com/BrokenString/p/9885460.html