NOIP 2014 day1第三题 飞扬的小鸟

1. 游戏界面是一个长为n ,高为 m 的二维平面,其中有k 个管道(忽略管道的宽度)。

3. 小鸟每个单位时间沿横坐标方向右移的距离为1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度X ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度Y 。小鸟位于横坐标方向不同位置时,上升的高度X 和下降的高度Y 可能互不相同。

4. 小鸟高度等于0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,,无法再上升。现在,请你判断是否可以完成游戏。如果可以 ,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

题解:首先应该很容易地想到70分的dp,设f[i][j]表示到第i列第j的高度所要的最小点击次数。

那么我们枚举从上一行按屏幕的次数,01背包求解,往下类似。

然而这样做复杂度会爆,所以向上就做完全背包。

换言之f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1); f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);//这一行是完全背包 复杂度O(nm);

然后注意一下靠近顶的格子不能超过,特殊转移一下,详情见代码,然后有管子的地方赋值为INF。

%%%__debug大神。

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#define INF 0x7fffffff/10const int MAXN=10001,MAXM=1001;int n,m,k,x[MAXN],y[MAXN],up[MAXN],down[MAXN],f[MAXN][MAXM];int min(int a,int b){return a<b?a:b;}int main(){freopen("bird.in","r",stdin);freopen("bird.out","w",stdout);scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=n;i++)scanf("%d %d",&x[i-1],&y[i-1]);for(int i=1;i<=k;i++){int a,b,c;scanf("%d %d %d",&a,&b,&c);down[a]=b;up[a]=c;}for(int i=1;i<MAXN;i++)for(int j=0;j<MAXM;j++)f[i][j]=INF;f[0][0]=INF;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)if(j>x[i-1])//up{f[i][j]=min(f[i][j],f[i-1][j-x[i-1]]+1);f[i][j]=min(f[i][j],f[i][j-x[i-1]]+1);}for(int j=m-x[i-1];j<=m;j++){f[i][m]=min(f[i][m],f[i-1][j]+1);f[i][m]=min(f[i][m],f[i][j]+1);}if(!down[i])down[i]=0;if(!up[i])up[i]=m+1;for(int j=down[i]+1;j<up[i];j++)if(j+y[i-1]<=m)//not 0 to mf[i][j]=min(f[i][j],f[i-1][j+y[i-1]]);for(int j=0;j<=down[i];j++)f[i][j]=INF;for(int j=m;j>=up[i];j–)f[i][j]=INF;f[i][0]=INF;}int ans=INF;for(int j=0;j<=m;j++)ans=min(ans,f[n][j]);if(ans!=INF)printf("1\n%d\n",ans);else{int cnt=0;for(int i=n-1;i>=0;i–){for(int j=0;j<=m;j++)if(f[i][j]<INF){ans=i;break;}if(ans<INF)break;}for(int i=0;i<=ans;i++)if(up[i]!=m+1&&up[i]!=0)cnt++;printf("0\n%d\n",cnt);}}

版权声明:本文为博主原创文章,未经博主允许不得转载。

人创造奇迹常常是在瞬间,

NOIP 2014 day1第三题 飞扬的小鸟

相关文章:

你感兴趣的文章:

标签云: