记录编号	185414	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-09-06 18:24:51	内存使用	1.59 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<deque>
using namespace std;
const int INF=0x7fffffff;
int W,H,tot=0;
int M=0;
int v[1010][110]={0},f[1010][110]={0},father[1010][110]={0};
int E;
void out()
{
	deque<int> Q;
	int tem=M;
	while(father[tem][E]!=0)
	{
		Q.push_back(E-father[tem][E]);
		E=father[tem][E];
		tem--;
		//cout<<E<<" "<<tem<<" "<<father[tem][E]<<endl;
	}
	for(int i=Q.size()-1;i>=0;i--)
	{
		printf("%d\n",Q[i]);
	}
}
void DP()
{
	for(int i=0;i<=M;i++)
		for(int j=0;j<=W;j++) f[i][j]=-INF;
	f[0][W/2+1]=v[0][W/2+1];
	for(int i=0;i<M;i++)
		for(int j=1;j<=W;j++)
		{
			if(f[i][j]>=0)
			{
				if(j+2<=W&&f[i][j]+v[i+1][j+2]>f[i+1][j+2])
				{
					f[i+1][j+2]=f[i][j]+v[i+1][j+2];
					father[i+1][j+2]=j;
					
				}
				if(j+1<=W&&f[i][j]+v[i+1][j+1]>f[i+1][j+1])
				{
					f[i+1][j+1]=f[i][j]+v[i+1][j+1];
					father[i+1][j+1]=j;
				}
				if(f[i][j]+v[i+1][j]>f[i+1][j])
				{
					f[i+1][j]=f[i][j]+v[i+1][j];
					father[i+1][j]=j;
			    }
				if(j-1>0&&f[i][j]+v[i+1][j-1]>f[i+1][j-1])
				{
					f[i+1][j-1]=f[i][j]+v[i+1][j-1];
					father[i+1][j-1]=j;
				}
				if(j-2>0&&f[i][j]+v[i+1][j-2]>f[i+1][j-2])
				{
					f[i+1][j-2]=f[i][j]+v[i+1][j-2];
					father[i+1][j-2]=j;
				}
				//cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<f[i+1][j]<<endl;
			}
		}
	int ans=0;
	for(int i=1;i<=W;i++)
	{
		if(f[M][i]>f[M][E])
		{
			ans=f[M][i];
			E=i;
		}
	}
	//cout<<E<<endl;
	//cout<<f[M][E]<<endl;
	if(M==0)
	{
		printf("%d\n",f[0][E]);
		if(f[0][E]) printf("0\n");
		return;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	scanf("%d%d",&W,&H);
	int t,x,V,s;
	while(scanf("%d%d%d%d",&t,&x,&V,&s)==4)
	{
		if((H-1)%V==0||t==0)
		{
		v[(H-1)/V+t][x]+=s;
		M=max(M,(H-1)/V+t);
		}
	}
	
	//cout<<f[M]<<endl;
	//for(int i=1;i<=W;i++)
	//	for(int j=1;j<=M;j++)
	//		cout<<i<<" "<<j<<" "<<v[j][i]<<endl;
	DP();
	//cout<<f[M][1]<<endl;
	out();
	return 0;
}