题解 | #免费馅饼#

Description

有一个大小为 $h \times n$ 的大方格，初始小人在位置 $[h][(n \dotplus 1) / 2]$ 。记小人的位置为 $pos$ ,每秒小人都能够移动至 $[max(1,pos - 2),min(n,pos \dotplus 2])$ 的范围内。

给不定数个苹果，对苹果 $p$ , 在 $t$ 时刻出现在 $[x,h]$ , 下落速度为 $v$ , 价值为 $val$ 。

求小人通过最优移动能够获得的最大价值和
打印小人每秒的移动策略

Solution

考虑 $DP$

不难想到DP数组 $f_{i,j}$ 的状态设置为小人在第 $i$ 秒，位于位置 $j$ 时获得的最大价值和。

$f_{i,j} = min(f_{i - 1,j-2/j-1/j/j \dotplus1/j \dotplus2}) \dotplus val_{i,j}$

$val_{i,j}$ 是小人在第 $i$ 秒，位于位置 $j$ 时能够获得的价值和

由于起始位置固定，不妨倒过来DP。

答案就是 $f_{0,(n \dotplus 1) / 2}$

求DP的路径只需要记录是怎么转移的即可。

code

#include <bits/stdc++.h>
#define ull unsigned long long int 
//#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 1e9 + 7,INF = 0x3f3f3f3f;

typedef pair<int,int> PII;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

int pre[N][100];
int f[N][100];
int p[N][100];

/*
f[i][j] 表示为第 i 秒在位置 j 收集到的最大值。
p[i][j] 表示为刚好第 i 秒在位置 j 可以收集到的价值之和1

f[i][j] = max(f[i + 1][j-2 ~ j+2]) + p[i][j];
*/


void slove(){
    int n = read(),h = read();
    int t,x,v,w,maxt = 0;
    while(scanf("%d%d%d%d",&t,&x,&v,&w) != EOF){
        if((h - 1) % v)continue;
        int times = t + (h - 1) / v;
        p[times][x] += w;
        maxt = max(maxt,times);
    }
    int star =(n + 1) /2;
    for(int i = maxt;~i;i--){
        for(int j = 1;j <= n; j++){
            if(j - 2 >= 1 && f[i][j] < f[i + 1][j - 2] + p[i][j]){//这坨有点丑哈
                pre[i][j] = -2;
                f[i][j] = f[i + 1][j - 2] + p[i][j];
            }
            if(j  - 1 >= 1 && f[i][j] < f[i + 1][j - 1] + p[i][j]){
                pre[i][j] = -1;
                f[i][j] = f[i + 1][j - 1] + p[i][j];
            }
            if(f[i][j] < f[i + 1][j] + p[i][j]){
                pre[i][j] = 0;
                f[i][j] = f[i + 1][j] + p[i][j];
            }
            if(j + 1 <= n && f[i][j] < f[i + 1][j + 1] + p[i][j]){
                pre[i][j] = 1;
                f[i][j] = f[i + 1][j + 1] + p[i][j];
            }
            if(j + 2 <= n && f[i][j] < f[i + 1][j + 2] + p[i][j]){
                pre[i][j] = 2;
                f[i][j] = f[i + 1][j + 2] + p[i][j];
            }
        }
    }

    cout << f[0][star] << endl;
    int i = 0;
    while (i < maxt){
        cout << pre[i][star] << endl;
        star += pre[i][star];
        i ++;
    }
}

signed main(){
    int T = 1;
    //T = read();
    while(T --){
        slove();
    }
    return 0;
}