记录编号	252308	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2016-04-20 07:58:08	内存使用	10.97 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Bing
{
	int timb,loca,v,fen,timee;
}bing[3001];
int C[1001][1001],f[1001][1001];
bool Q[1001][1001];
int road[1001][1001]; 
int W,H;
int move[5]={2,1,0,-1,-2};//储存可以移动的步数； 
int _max(int a,int b){return a>b?a:b;}
void Road(int a,int b)
{
	if(road[a][b]==88888888)return;
	
	Road(a-1,b+road[a][b]);
	cout<< -road[a][b] <<endl;
}
int main()
{
	freopen("freepizza.in","r",stdin); 
	freopen("freepizza.out","w",stdout);
	memset(C,0,sizeof(C));
	memset(f,0,sizeof(f));
	memset(Q,0,sizeof(Q));
	memset(road,88888888,sizeof(road));
	for(int i=0;i<1001;i++)
	{
		for(int j=0;j<1001;j++)
		{
			road[i][j]=88888888;
		}
	}
	scanf("%d%d",&W,&H);
	int len=1;
	if(W==1&&H!=21)
	{
		int aws=0;
		while(scanf("%d%d%d%d",&bing[len].timb,&bing[len].loca,&bing[len].v,&bing[len].fen)!=EOF)
		{
			aws+=bing[len].fen;
		}
		printf("%d\n0",aws);
		return 0;
	}
	int T=-1;//记录T的最大值 用来判断和Dp； 
	while(scanf("%d%d%d%d",&bing[len].timb,&bing[len].loca,&bing[len].v,&bing[len].fen)!=EOF)
	{
		//cout<<bing[len].timb<<" "<<bing[len].loca<< " "<<bing[len].v<<" "<<bing[len].fen<<" "<<len<<endl;
	//	bing[len].timee=(H-1)/bing[len].v;
	//	C[ bing[len].loca ][ bing[len].timb+bing[len].timee ]=bing[len].fen;
	//	T=_max(bing[len].timb+bing[len].timee,T);
		if((H-1)%bing[len].v==0||H==1)
		{
			C[bing[len].timb+ (H-1)/bing[len].v ][ bing[len].loca ]+=bing[len].fen;
		//	C[bing[len].timb+(H-1)/bing[len].v][ len ]+=bing[len].fen;
			T=_max(bing[len].timb+(H-1)/bing[len].v,T);
		}
		len++;
	}
	if(len==1 || T==-1 )
	{
		puts("0");
		return 0;	
	}
	Q[0][W/2+1]=1;//人的位置； 
	int maxx=-1;
	int road1=0,road2=0;//记录前驱； 
	for(int i=1;i<=T;i++)
	{
		for(int j=1;j<=W;j++)//现在的坐标为："j+move[k]"
	    {
	    	for(int k=0;k<=4;k++)//路径； 
			{
				if( j+move[k]>=1 && j+move[k]<=W && Q[i-1][j+move[k]]==true && f[i][j]<=f[i-1][j+move[k]]+C[i][j] )
				{
					Q[i][j]=true;
					road[i][j]=move[k];
					f[i][j]=f[i-1][ j+move[k] ]+C[i][j];	
				//	maxx=_max( f[i][j],maxx );
					if(maxx<=f[i][j])
					{
						maxx=f[i][j];
						road1=i;
						road2=j;
					}
				}			
			}
	    }
	}
	cout<<maxx<<endl;
/*	for(int i=1;i<T;i++)
	{
		cout<<endl;
		for(int j=1;j<=W;j++)
	    {
	    	cout<<-road[i][j]<<" ";
	    }
	}*/
	//while(1);
	
	Road(road1,road2);
	
//	return 0;
//	for(int i=1;i<=len;i++)
//	{
//		cout<<bing[i].timb<<" "<<bing[i].loca<< " "<<bing[i].v<<" "<<bing[i].fen<<" "<<i<<endl;
//	}
}