[NOI1998]免费馅饼

第一行是用空格隔开的两个正整数，分别给出了舞台的宽度W（1到99之间的奇数）和高度H（1到100之间的整数）。
接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0到1000秒），水平位置、下落速度（1到100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。
输入文件中同一行相邻两项之间用一个或多个空格隔开

第一行给出了一个正整数，表示你的程序所收集的最大分数之和。
其后的每一行依时间顺序给出了游戏者每秒的决策。输出0表示原地不动、1或2表示向右移动一步或两步、-1 或-2表示向左移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 904K, 提交时间: 2022-10-11 21:44:10

#include<bits/stdc++.h>
using namespace std;

int  dp[1010][1010],a[1010][1010],way[1010][1010];
int main()
{
	int n,m,cnt=0; cin>>n>>m;
	
	int x,y,z,q,co=0,t=0;
	while(cin>>x>>y>>z>>q){
        if ((m-1) % z==0){ 
	 a[x+(m-1)/z][y]+=q;	
    
	 t=max(t,x+(m-1)/z);}
	}
	
	
	
	for(int i=t;i>=0;i--)
	 for(int j=1;j<=n;j++)
	  for(int k=-2;k<=2;k++)
	{  if(dp[i][j]<dp[i+1][j+k]+a[i][j])way[i][j]=k,
	  dp[i][j]=dp[i+1][j+k]+a[i][j];	
	}

 cout<<dp[0][(n+1)/2]<<endl;
	
	for(int i=0,j=(n+1)/2;i<t;j+=way[i][j],i++)
	cout<<way[i][j]<<endl;
     
     
	
	
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 904K, 提交时间: 2023-01-12 19:14:15

#include<bits/stdc++.h>
using namespace std;
int f[1010][1010],g[1010][1010],way[1010][1010];
int main(){

	int n,m,cnt,x,y,z,q,t;
	cin>>n>>m;
	while(cin>>x>>y>>z>>q){
		if((m-1)%z==0){
			g[x+(m-1)/z][y]+=q;
			t=max(t,x+(m-1)/z);
		}
	}
	for(int i=t;i>=0;i--)
	for(int j=1;j<=n;j++)
	for(int k=-2;k<=2;k++){
		if(f[i][j]<f[i+1][j+k]+g[i][j])way[i][j]=k,f[i][j]=f[i+1][j+k]+g[i][j];
	}
	cout<<f[0][(n+1)/2]<<endl;
	for(int i=0,j=(n+1)/2;i<t;j+=way[i][j],i++)cout<<way[i][j]<<endl;
	return 0;
}

详情