SERKOI最新推出了一种叫做“免费馅饼”的游戏。
游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落，下落速度1格/秒。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。
免费馅饼可以用动态规划算法解决。
状态方程如下：
F[i][j]=max(F[i-1],F[j-k])+A[i][j];(-2<=k<=2)
表示第 i 秒在第 j 个格中收集到的最大饼值。
A[i][j] 表示第i秒中方格j可以收集到的饼值。
动态规划解免费馅饼代码如下:
#include<cstring>
#include<stdlib.h>
int w=0,h=0,t=0;
int all=0,at=0,ak=0;
int a[1010][110];
int f[1010][110];
int g[1010][110];
FILE *fp,*fp2;
void output(int at,int ak)
{
if(at<=0)
return;
output(at-1,ak-g[at][ak]);
fprintf(fp2,“%d\n“,g[at][ak]);
}
int main()
{
fp=fopen(“in.txt”,“r”);
fp2=fopen(“out.txt”,“w”);
fscanf(fp,“%d%d”,&w,&h); //读取w和h
for(int i=0;i<=100;++i)//初始化
for(int j=1;j<=100;++j)
{
f[i][j]=-1000;
a[i][j]=0;
g[i][j]=0;
}
int t1,w1,s1;//时间,位置,分数
while(fscanf(fp,“%d%d%d”,&t1,&w1,&s1)!=EOF){
a[t1+(h-1)][w1]+=s1;
}
fclose(fp);
t=t1+(h-1); //总时间
f[0][(w+1)/2]=a[0][(w+1)/2];//0时刻
for(int i=1;i<=t;++i){
for(int j=1;j<=w;++j){
for(int k=2;k>=-2;k-)
{
if(j-k>0&&j-k<=w&&f[i-1][j-k]>f[i][j]){
f[i][j]=f[i-1][j-k];
g[i][j]=k;
}
}
f[i][j]+=a[i][j];
if(f[i][j]>all){
all=f[i][j];
at=i;
ak=j;
}
}
}
fprintf(fp2,“%d\n“,all);
output(at,ak);
fclose(fp2);
return 0;
}
样例输入
3 3
0 1 5
0 2 3
1 2 3
1 3 4
样例输出
9
-1
0
2
哈哈 这种类似的游戏我以前用VB编过。。。不过大学之后 就再没接触计算机语言方面的东西了。。
ps 我给你发邮件了 期待答复~