记录编号	446548	评测结果	WAAAWA
题目名称	[NOI 1998]免费馅饼	最终得分	66
用户昵称	Arrow	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-09-08 16:22:20	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define MAXW 110
#define MAXT 1010

	int w,h,max_t=0,start_pos=0,ans=0;
	int g[MAXW][MAXT]={0},f[MAXW][MAXT]={0},p[MAXW][MAXT]={0};
		// f[i][j] means in the position i and at time j the max points
		// g[i][j] notes the number of pizzas which are in the position i and at time j
		// p[i][j] notes the choice which leads to state f[i][j]
	int move[5]={2,1,0,-1,-2};// four kinds of movements

void work()
{
	start_pos=(1+w)/2;
	memset(f,-1,sizeof(f));
	memset(p,-1,sizeof(p));
	f[start_pos][0]=g[start_pos][0];
	if(f[start_pos][0]!=0)
		p[start_pos][0]=2;
	for(int j=1;j<=max_t;j++)
	{
		for(int i=1;i<=w;i++)
		{
			for(int k=5;k>=0;k--) //k 代表到达该状态所使用的方案，为了保证字典序应尽量由左边转移来
			{
				if(i+move[k]<1||i+move[k]>w) continue;
				//if(f[i+move[k]][j-1]!=-1)
					if(f[i][j]<f[i+move[k]][j-1]+g[i][j])
					{
						f[i][j]=f[i+move[k]][j-1]+g[i][j];
						p[i][j]=k;
					}
			}
		}
	}
	
}

int getans()
{
	int max_i,max_j;
	for(int i=1;i<=w;i++)
	{
		for(int j=0;j<=max_t;j++)
		{
			if(ans<f[i][j])
			{
				ans=f[i][j];
				max_i=i;
				max_j=j;
			}
		}
	}
	printf("%d\n",ans);
	int cur_i=max_i,cur_j=max_j;
	int tmp[MAXT]={0};
	if(cur_j==0&&ans!=0)
	{
		printf("%d\n",move[p[cur_i][cur_j]]);
		return 0;
	}
	while(cur_j>=0)
	{
		tmp[cur_j-1]=-move[p[cur_i][cur_j]];
		cur_i+=move[p[cur_i][cur_j]];
		cur_j--;  //time move 1 second forward
	}
	for(int i=0;i<max_j;i++)
		printf("%d\n",tmp[i]);
	return 1;
}

int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	scanf("%d%d",&w,&h);
	int st,sp,speed,val;
	while(scanf("%d%d%d%d",&st,&sp,&speed,&val)!=EOF)
	{
		if(((h-1)/speed>=1&&(h-1)%speed==0)||st==0)
		{
			g[sp][(h-1)/speed+st]+=val;
			max_t=max(max_t,(h-1)/speed+st);
		}
	}
	work();
	getans();
return 0;
}