免費餡餅

題目描述

SERKOI最新推出了一種叫做“免費餡餅”的游戲:游戲在一個舞臺上進行，舞臺的寬度為W格，天幕的高度為H格，游戲者占一格，開始時游戲者站在舞臺的正中央，手里拿著一個托盤，下圖為天幕的高度為4格時某一個時刻游戲者接餡餅的情景，

游戲開始后，從舞臺天幕頂端的格子中不斷出現餡餅并垂直下落，游戲者左右移動去接餡餅，游戲者每秒可以向左或向右移動一格或兩格，也可以站在原地不動，
餡餅有很多種，游戲者事先根據自己的口味，對各種餡餅依次打了分，同時，在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位，
當餡餅在某一秒末恰好到達游戲者所在的格子中，游戲者就收集到了這塊餡餅，
寫一個程式，幫助我們的游戲者收集餡餅，使得所收集餡餅的分數之和最大，

輸入格式：

輸入檔案的第一行是用空格隔開的兩個正整數，分別給出了舞臺的寬度W（1到99之間的奇數）和高度H（1到100之間的整數），
接下來依餡餅的初始下落時間順序給出了所有餡餅的資訊，每一行給出了一塊餡餅的資訊，由四個正整陣列成，分別表示了餡餅的初始下落時刻（0到1000秒），水平位置、下落速度（1到100）以及分值，游戲開始時刻為0，從1開始自左向右依次對水平方向的每格編號，
輸入檔案中同一行相鄰兩項之間用一個或多個空格隔開，

輸出格式：

輸出檔案的第一行給出了一個正整數，表示你的程式所收集的最大分數之和，

輸入樣例

3 3
0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4

輸出樣例

12

思路：我們正著想會發現些許的問題：

• 比如我們每移動一次，所有的煎餅都會往下面走幾格，但這樣維護不免太復雜了，我們不妨反著想：

我們可以讓小人從下往上走，比如這樣

這樣我們就不用去維護當前這個餡餅到底走到了哪里，然后因為餡餅下落的速度不一樣，所以在一開頭就可以做一個操作，把每一個餡餅的高度設定為當前的高度除以當前的下落的速度，并且把這個餡餅的分數也設到這個地方，

這樣從下往上走就可以起到等同的作用

設 d p [ i ] [ j ] dp[i][j] dp[i][j]為當前走到了第 i i i行的第 j j j列，

我們再想想 （ i ， j ） （i，j） （i，j）可以從哪些地方走過來

（ i ， j ） （i，j） （i，j）這個地方，可以從 （ i ? 1 ， j ? 2 ） （i - 1，j - 2） （i?1，j?2）， （ i ? 1 ， j + 1 ） （i - 1，j+1） （i?1，j+1）， （ i ， j ） （i，j） （i，j）， （ i ? 1 ， j ? 1 ） （i - 1，j - 1） （i?1，j?1）， （ i ? 1 ， j ? 2 ） （i - 1，j - 2） （i?1，j?2）過來，所以狀態轉移方程可以這么寫：

d p [ i ] [ j ] = m a x ( d p [ i ? 1 ] [ j ? 2 ] , d p [ i ? 1 ] [ j ? 1 ] , d p [ i ? 1 ] [ j ] , d p [ i ? 1 ] [ j + 1 ] , d p [ i ? 1 ] [ j + 2 ] ) + a [ i ] [ j ] dp[i][j]=max(dp[i-1][j-2], dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1], dp[i-1][j+2]) + a[i][j] dp[i][j]=max(dp[i?1][j?2],dp[i?1][j?1],dp[i?1][j],dp[i?1][j+1],dp[i?1][j+2])+a[i][j]
a [ i ] [ j ] a[i][j] a[i][j]，表示這個位置的分數

• 因為是求最大分數之和，所以取五個值的最大值加上當前這個位置的價值，

#include <bits/stdc++.h>

using namespace std;
#define MAXN 1005
#define MAXM 105
int a[MAXN][MAXM], dp[MAXN][MAXM];
int w, h, t, x, v, s, ti, mx, et;
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &w, &h);
    h--;
    while(scanf("%d %d %d %d", &t, &x, &v, &s) != EOF)
    {
        if(h % v == 0)
            et = h / v + t;
        a[et][x] += s;
        ti = max(ti, et);
    }
    if(w == 1 && h == 0)
    {
        int ans = 0;
        for(register int i = 0; i <= ti; i++)
            ans += a[i][1];
        printf("%d", ans);
        return 0;
    }
    dp[0][w / 2 + 1] = 0;
    for(int i = 1; i <= ti; i++)
        for(int j = 1; j <= w; j++)
            for(int k = -2; k <= 2; k++)
            {
                if(j + k < 1 || j + k > w)
                    continue;
                if(dp[i][j] < dp[i - 1][j + k] + a[i][j])
                    dp[i][j] = dp[i - 1][j + k] + a[i][j];
            }
    for(int i = 1; i <= ti; i++)
        for(int j = 1; j <= w; j++)
            mx = max(mx, dp[i][j]);
    printf("%d\n",mx);
    return 0;
}

完結撒花★,°:.☆(￣▽￣)/$:.°★ ，