记录编号	164317	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-05-30 10:11:04	内存使用	1.99 MiB

#include <iostream>
#include <fstream>
#include <queue>
#define cin fi
#define cout fo
 
using namespace std;
 
ifstream fi("freepizza.in");
ofstream fo("freepizza.out");
const int MAXW = 110, MAXH = 101;
int w, h, f[MAXW][2000] = {0}, nx, ny = 0, hh = 0, dp[MAXW][2000] = {0};
bool ans = false;
     
void print(int nh, int d, int x)
{
    if(nh > hh)
        return;
    for(int i = max(1, x - 2); i <= min(w, x + 2); i ++)
        if(f[nh - 1][x] + dp[nh][i] == d)
        {
        	cout << i - x << endl;
            ans = true;
            print(nh + 1, dp[nh][i], i);
            return;
        }
    return;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin >> w >> h;
    nx = w / 2 + 1;
    int t, x, v, p;
    while(cin >> t >> x >> v >> p)
    {
        if((h - 1) % v == 0 || w == 1)
        {
        	f[t + (h - 1) / v][x] += p;
        	hh = max(hh, t + (h - 1) / v);
        }
    }
     
    for(int i = 1; i <= w; i ++)
        dp[hh][i] = f[hh][i];
    for(int i = hh - 1; i >= 0; i --)
        for(int j = max(1, nx - 2 * i); j <= min(w, nx + 2 * i); j ++)
        {
            if(j - 2 > 0)
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 2]);
            if(j - 1 > 0)
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1]);
            if(j + 1 <= w)
                dp[i][j] = max(dp[i][j], dp[i + 1][j + 1]);
            if(j + 2 <= w)
                dp[i][j] = max(dp[i][j], dp[i + 1][j + 2]);
            dp[i][j] = max(dp[i][j], dp[i + 1][j]);
            dp[i][j] += f[i][j];
        }
         
    cout << dp[ny][nx] << endl;
    print(1, dp[ny][nx], nx);
    if(dp[ny][nx] != 0 && (! ans))
    	cout << 0;
    /*cout << endl << endl;
    for(int i = 0; i <= hh; i ++)
    	cout << dp[i][1] << endl;*/
    return 0;
}