JZOJ – 5770 可爱精灵宝贝

Time Limit : 1000ms
Memory Limit : 512MB

Description

Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由 $1$ 到$n$ 。
刚开始玩家在 $k$ 号房子前。有 $m$ 个精灵，第 $i$ 只精灵在第 $A[i]$ 栋房子前，分值是 $B[i]$ ，以及它在 $T[i]$ 秒内（含）存在，之后消失。Branimirko可以选择移动至相邻的房子，耗时1秒。抓住精灵不需要时间，精灵被抓住后消失。时间从第1秒开始。Branimirko能最多获得多少分值和。

Input

输入的第1行为三个正整数 $n，k，m $。
接下来m行描述精灵的信息，分别为 $A[i]，B[i]，T[i]$。

Output

输出Branimirko能最多获得多少分值和。

Sample Input

Sample Output

Data Constraint

20%的数据：m≤10
40%的数据：m≤20
k≤n≤1000,m≤100,A[i] ≤N,B[i] ≤100,T[i] ≤2000，所有数为正整数。

解题思路

观察题目，可以发现Branimirko走的轨迹是来回往复的，并且一次比一次走的离起点远。

我们可以用区间DP解决这道题目，令状态 $f[i][j][t][0/1] $ 表示现在左端点是 $i$，右端点是 $j$，用时 $t$, 目前处于左端点/右端点

转移就是标准的区间DP转移，可以从 $l$ 走到 $r+1$ , $r$ 走到 $r+1$, $r$ 走到 $l-1$ 或 $l$ 走到 $l-1$

最后统计 $f[i][j][t][0/1]$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100 + 10;
const int MAXT = 2000 + 10;

int n, k, m;

struct Go{
    int a, b, t;
};

Go data[MAXN];

inline bool cmp(Go x, Go y){
    return x.a < y.a;
}

int maxt;

int f[MAXN][MAXN][MAXT];
int g[MAXN][MAXN][MAXT];

int main(){

    freopen("go.in", "r", stdin);
    freopen("go.out", "w", stdout);

    scanf("%d%d%d", &n, &k, &m);

    for(register int i=1; i<=m; i++){
        scanf("%d%d%d", &data[i].a, &data[i].b, &data[i].t);
        maxt = max(maxt, data[i].t);
    }

    sort(data+1, data+m+1, cmp);


    for(register int i=1; i<=m; i++){
        for(register int j=1; j<=m; j++){
            for(register int k=0; k<=maxt; k++){
                f[i][j][k] = -0x3f3f3f3f;
                g[i][j][k] = -0x3f3f3f3f;
            }
        }
    }


    for(register int i=1; i<=m; i++){
        int delta = abs(k - data[i].a) + 1;
        for(register int t=maxt; t>=delta; t--){
            if(delta <= data[i].t){
                f[i][i][t] = data[i].b; 
                g[i][i][t] = data[i].b;
            }else{
                f[i][i][t] = 0;
                g[i][i][t] = 0;
            }

        }
    }


    for(register int length=2; length<=m; length++){
        for(register int l=1; l<=m-length+1; l++){
            int r = l + length - 1;
            for(register int t = 0; t<=maxt; t++){

                int t1 = abs(data[r].a - data[r-1].a);

                if(t > t1){
                    if(t <= data[r].t)
                        f[l][r][t] = max(f[l][r][t], f[l][r-1][t-t1] + data[r].b);
                    else
                        f[l][r][t] = max(f[l][r][t], f[l][r-1][t-t1]);
                }

                int t2 = abs(data[r].a - data[l].a);
                if(t > t2){
                    if(t <= data[r].t)
                        f[l][r][t] = max(f[l][r][t], g[l][r-1][t-t2] + data[r].b);
                    else
                        f[l][r][t] = max(f[l][r][t], g[l][r-1][t-t2]);
                }

                int t3 = abs(data[l+1].a - data[l].a);
                if(t > t3){
                    if(t <= data[l].t)
                        g[l][r][t] = max(g[l][r][t], g[l+1][r][t-t3] + data[l].b);
                    else
                        g[l][r][t] = max(g[l][r][t], g[l+1][r][t-t3]);
                }

                if(t > t2){
                    if(t <= data[l].t)
                        g[l][r][t] = max(g[l][r][t], f[l+1][r][t-t2] + data[l].b);
                    else
                        g[l][r][t] = max(g[l][r][t], f[l+1][r][t-t2]);
                }
            }
        }
    }

    int ans = 0;

    for(register int l=1; l<=m; l++){
        for(register int r=l; r<=m; r++){
            for(register int t=0; t<=maxt; t++){
                ans = max(ans, f[l][r][t]);
                ans = max(ans, g[l][r][t]);
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

[题解] JZOJ – 5770 可爱精灵宝贝

BLOG