描述
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。
图片
为了简化问题，我们对游戏规则进行了简化和改编：
游戏界面是一个长为 n，高为 m 的二维平面，其中有k 个管道（忽略管道的宽度）。
小鸟始终在游戏界面内移动。小鸟从游戏界面最左边 任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为 1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 X，每个单位时间可以点击多次，效果叠加； 如果不点击屏幕，小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时，上 升的高度 X 和下降的高度 Y 可能互不相同。
小鸟高度等于 0 或者小鸟碰到管道时，游戏失败。小鸟高度为 m 时，无法再上升。
现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。
格式
输入格式
第 1 行有 3 个整数 n，m，k，分别表示游戏界面的长度，高度和水管的数量，每两个 整数之间用一个空格隔开；
接下来的 n 行，每行 2 个用一个空格隔开的整数 X 和 Y，依次表示在横坐标位置 0~n-1 上玩家点击屏幕后，小鸟在下一位置上升的高度 X，以及在这个位置上玩家不点击屏幕时， 小鸟在下一位置下降的高度 Y。
接下来 k 行，每行 3 个整数 P，L，H，每两个整数之间用一个空格隔开。每行表示一个管道，其中 P 表示管道的横坐标，L 表示此管道缝隙的下边沿高度为 L，H 表示管道缝隙上边沿的高度（输入数据保证 P 各不相同，但不保证按照大小顺序给出）。
输出格式
共两行。
第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。 第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。
样例1
样例输入1[复制]
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
样例输出1[复制]
1
6
样例2
样例输入2[复制]
10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10
样例输出2[复制]
0
3
【题解】
完全背包(100)、多重背包(85分)、记忆化搜索(65分)、爆搜(50分)
记忆化搜索就是加个f[i][j]记录到i,j这个点的最小点击次数;
多重背包和完全背包也是
用一个f[i][j];
多重背包会好理解点
f[i][j] =min(f[i][j],f[i-1][j-k*a[i-1][0]]+1);
f[i][j] = min(f[i][j],f[i-1][j+a[i-1][1]]);
完全背包可以省去那个k层的循环
f[i][j] = min(f[i][j],f[i-1][j-a[i-1][0]]+1);
f[i][j] = min(f[i][j],f[i][j-a[i-1][0]]+1);
上面两步要紧接着写;(不懂就去看完全背包！);
下面这一步如果和上面那步一起写会造成错解;
f[i][j] = min(f[i][j],f[i-1][j+a[i-1][1]]);
【爆搜】(50分)
#include <cstdio>
#include <cstring>
#define MAXN 1001
#define MAXM 101
int n,m,k,a[MAXN][2],ans,maxstep=0;
bool bo[MAXN][MAXM],haved[MAXN];
void pre()
{
memset(bo,true,sizeof(bo));
}
void input_data()
{
scanf("%d%d%d",&n,&m,&k);
ans=n*4;
for (int i=0;i<=n-1;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
for (int i=1;i<=k;i++)
{
int x,down,up;
scanf("%d%d%d",&x,&down,&up);
haved[x]=true;
for (int j=1;j<=down;j++) bo[x][j]=false;
for (int j=up;j<=m;j++) bo[x][j]=false;
}
}
void search(int xi,int highi,int toti,int numi)
{
int x=xi,high=highi,tot=toti,num=numi;
if (num>maxstep) maxstep=num;
if (tot>=ans) return;
if (x==n)
{
ans=tot;
return;
}
bool judge=false;
for (int i=1;i<=3;i++)
{
int temp=high+i*a[x][0];
if (temp>m)
{
temp=m;
judge=true;
}
if (bo[x+1][temp])
if (haved[x+1])
search(x+1,temp,tot+i,num+1);else
search(x+1,temp,tot+i,num);
if (judge) break;
}
int temp=high-a[x][1];
if ( temp>0 && bo[x+1][temp])
if (haved[x+1])
search(x+1,temp,tot,num+1);else
search(x+1,temp,tot,num);
}
void pre_search()
{
for (int i=1;i<=m;i++)
search(0,i,0,0);
}
void output_ans()
{
bool judge=ans==(n*4);
if (judge)
printf("%d\n%d\n",0,maxstep);
else
printf("%d\n%d\n",1,ans);
}
int main()
{
//freopen("bird.in","r",stdin);
//freopen("bird.out","w",stdout);
pre();
input_data();
pre_search();
output_ans();
//fclose(stdin);
//fclose(stdout);
return 0;
}【记忆化搜索】(65分)
#include <cstdio>
#include <cstring>
#define MAXN 10001
#define MAXM 1001
const int INF = 0x3f3f3f3f;
int n,m,k,a[MAXN][2],ans,maxstep=0;
bool bo[MAXN][MAXM],haved[MAXN];
int f[MAXN][MAXM];
void pre()
{
memset(bo,true,sizeof(bo));
}
void input_data()
{
scanf("%d%d%d",&n,&m,&k);
ans=n*4;
for (int i=0;i<=n-1;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
for (int i=1;i<=k;i++)
{
int x,down,up;
scanf("%d%d%d",&x,&down,&up);
haved[x]=true;
for (int j=1;j<=down;j++) bo[x][j]=false;
for (int j=up;j<=m;j++) bo[x][j]=false;
}
}
void search(int xi,int highi,int toti,int numi)
{
int x=xi,high=highi,tot=toti,num=numi;
if (f[x][high]<=toti)
return;
f[x][high] = tot;
if (num>maxstep) maxstep=num;
if (tot>=ans) return;
if (x==n)
{
ans = tot;
return;
}
bool judge=false;
for (int i=1;;i++)
{
int temp=high+i*a[x][0];
if (temp>=m)
{
temp=m;
judge=true;
}
if (bo[x+1][temp])
if (haved[x+1])
search(x+1,temp,tot+i,num+1);else
search(x+1,temp,tot+i,num);
if (judge) break;
}
int temp=high-a[x][1];
if ( temp>0 && bo[x+1][temp])
if (haved[x+1])
search(x+1,temp,tot,num+1);else
search(x+1,temp,tot,num);
}
void pre_search()
{
for (int i=1;i<=m;i++)
search(0,i,0,0);
}
void output_ans()
{
bool judge=ans==(n*4);
if (judge)
printf("%d\n%d\n",0,maxstep);
else
printf("%d\n%d\n",1,ans);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
memset(f,INF,sizeof(f));
pre();
input_data();
pre_search();
output_ans();
return 0;
}【多重背包】(85分)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 10001
#define MAXM 1001
using namespace std;
const int INF = 0x3f3f3f3f;
int n,m,k,a[MAXN][2],ans,maxstep=0;
bool haved[MAXN];
int f[MAXN][MAXM];
int guan[MAXN][2];
void input_data()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=0;i<=n-1;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
for (int i=1;i<=k;i++)
{
int x,down,up;
scanf("%d%d%d",&x,&down,&up);
haved[x]=true;
guan[x][0] = down;
guan[x][1] = up;
}
}
bool hefa(int x,int temp)
{
if (!haved[x] || (haved[x]&&guan[x][0]<temp && temp < guan[x][1]))
return true;
return false;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
memset(f,INF,sizeof(f));
input_data();
for (int i = 1;i <= m;i++)
f[0][i] = 0;
for (int i = 0;i <= n-1;i++)
{
bool added = false;
int down = 1,up = m;
if (haved[i])
down = guan[i][0]+1,up = guan[i][1]-1;
for (int j = down;j<= up;j++)
{
int ne = j-a[i][1];
if (ne>=1)
{
if (hefa(i+1,ne))
if (f[i+1][ne]>f[i][j])
{
f[i+1][ne] = f[i][j];
if (haved[i+1]&&!added)
{
added = true;
maxstep++;
}
}
}
for (int t = 1;;t++)
{
ne = j+t*a[i][0];
if (ne>=m)
ne = m;
if (hefa(i+1,ne))
{
if (f[i+1][ne]>f[i][j]+t)
{
f[i+1][ne] = f[i][j]+t;
if (haved[i+1]&&!added)
{
added = true;
maxstep++;
}
}
}
if (ne==m)
break;
}
}
}
// for (int i = m;i>=1;i--)
// printf("%d %d\n",f[1][i],f[2][i]);
// return 0;
int ans = f[n][1];
for (int i = 2;i <= m;i++)
ans = min(ans,f[n][i]);
if (ans < INF)
{
puts("1");
printf("%d\n",ans);
}
else
{
puts("0");
printf("%d\n",maxstep);
}
return 0;
}【完全背包】(100分)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 10001
#define MAXM 1001
using namespace std;
const int INF = 0x3f3f3f3f;
int n,m,k,a[MAXN][2],ans,maxstep=0;
bool haved[MAXN];
int f[MAXN][MAXM];
int guan[MAXN][2];
void input_data()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=0;i<=n-1;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
for (int i=1;i<=k;i++)
{
int x,down,up;
scanf("%d%d%d",&x,&down,&up);
haved[x]=true;
guan[x][0] = down;
guan[x][1] = up;
}
}
bool hefa(int x,int temp)
{
if (!haved[x] || (haved[x]&&guan[x][0]<temp && temp < guan[x][1]))
return true;
return false;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
memset(f,INF,sizeof(f));
input_data();
for (int i = 1;i <= m;i++)
f[0][i] = 0;
for (int i = 1;i <= n;i++)
{
bool added = false;
for (int j = 1;j <= m;j++)
{
if (j > a[i-1][0])
{
f[i][j] = min(f[i][j],f[i-1][j-a[i-1][0]]+1);
f[i][j] = min(f[i][j],f[i][j-a[i-1][0]]+1);
}
if (j==m)
{
for (int t = m-a[i-1][0];t <= m;t++)
{
f[i][j] = min(f[i][j],f[i-1][t]+1);
f[i][j] = min(f[i][j],f[i][t]+1);
}
}
}
int down = 1,up = m;
if (haved[i])
down = guan[i][0]+1,up = guan[i][1]-1;
for (int j = down;j<= up;j++)
{
int pre = j+a[i-1][1];
if (pre<=m)
{
if (hefa(i-1,pre))
f[i][j] = min(f[i][j],f[i-1][pre]);
}
if (haved[i] && f[i][j]<INF && !added)
{
added = true;
maxstep++;
}
}
if (haved[i])
{
for (int j = 1;j <= guan[i][0];j++)
f[i][j] = INF;
for (int j = guan[i][1];j <= m;j++)
f[i][j] = INF;
}
}
int ans = f[n][1];
for (int i = 2;i <= m;i++)
ans = min(ans,f[n][i]);
if (ans < INF)
{
puts("1");
printf("%d\n",ans);
}
else
{
puts("0");
printf("%d\n",maxstep);
}
return 0;
}