记录编号	575106	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	[]~(￣▽￣)~*	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-03 12:29:31	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std; 
const int MAXT=1001,MAXW=101,INF=0x7FFFFFFF;
using namespace std;
int W,H,N,T,Ans,AT,AP;
int F[MAXT][MAXW],V[MAXT][MAXW],G[MAXT][MAXW];
int main()
{
	int i,j,t,p,v,s,dt;
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	scanf("%d%d",&W,&H);
	while (scanf("%d%d%d%d",&t,&p,&v,&s)!=EOF)
		if ((H-1)%v==0 || t==0)
		{
			dt=t+(H-1)/v;
			if (dt>T) T=dt;
			V[dt][p]+=s;
		}
	for (j=0;j<=T;j++)
		for (i=1;i<=W;i++)
			F[j][i]=-INF;
	p=(W+1)/2;
	Ans=F[0][p]=V[0][p];
	for (i=1;i<=T;i++)
	{
		for (j=1;j<=W;j++)
		{
			if (j-2>0 && F[i-1][j-2]>F[i][j])
			{
				F[i][j]=F[i-1][j-2];
				G[i][j]=2;
			}
			if (j-1>0 && F[i-1][j-1]>F[i][j])
			{
				F[i][j]=F[i-1][j-1];
				G[i][j]=1;
			}
			if (F[i-1][j]>F[i][j])
			{
				F[i][j]=F[i-1][j];
				G[i][j]=0;
			}
			if (j+1<=W && F[i-1][j+1]>F[i][j])
			{
				F[i][j]=F[i-1][j+1];
				G[i][j]=-1;
			}
			if (j+2<=W && F[i-1][j+2]>F[i][j])
			{
				F[i][j]=F[i-1][j+2];
				G[i][j]=-2;
			}
			F[i][j]+=V[i][j];
			if (F[i][j]>Ans)
			{
				Ans=F[i][j];
				AT=i;
				AP=j;
			}
		}
	}
	int Ar[MAXT];
	for (i=AT,j=AP;i>0;i--)
	{
		Ar[i]=G[i][j];
		j-=G[i][j];
	}
	printf("%d\n",Ans);
	if (T==0 && Ans!=0)
		printf("0\n");
	for (i=1;i<=AT;i++)
		printf("%d\n",Ar[i]);
	return 0;
}