[离散化][区间DP]JZOJ 5770 可爱精灵宝贝

日常黑Pokeman Go

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

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23
 

Sample Output

115
 

 

Data Constraint

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

 

Hint

很遗憾，它恰好不能抓住在一号房子前的精灵。
如果T[1]改成5，答案就是145

分析

比赛的时候居然打了一个不知道什么鬼的居然离散了时间的DP

正解区间DP，设f[l][r][t]为所用时间为t，经过了l~r，现在在r的最大分值，g[l][r][t]，类似，不过在l

预处理：离散化房屋编号

然后从l~r向l-1~r或l~r+1转移

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
int f[101][101][4001],g[101][101][4001];
struct Elf {
    int a,b,t;
}a[102];
int n,m,k,mxt,bg;

bool Cmp(Elf a,Elf b) {
    return a.a<b.a;
}
 
int main() {
    freopen("go.in","r",stdin);
    freopen("go.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].t),mxt=max(mxt,a[i].t);
    a[0].a=k;a[0].b=0;a[0].t=1;
    sort(a,a+m+1,Cmp);
    for (int i=0;i<=m;i++)
    if (a[i].a==k&&a[i].t==1) {bg=i;break;}
    memset(f,-0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    f[bg][bg][1]=g[bg][bg][1]=0;
    for (int t=1;t<=mxt;t++)
    for (int l=bg;l>=0;l--)
    for (int r=bg;r<=m;r++) {
        if (r<m) {
            f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]);
            f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]);
            if (a[r+1].a-a[r].a+t<=a[r+1].t)
            f[l][r+1][a[r+1].a-a[r].a+t]=max(f[l][r+1][a[r+1].a-a[r].a+t],f[l][r][t]+a[r+1].b);
            if (a[r+1].a-a[l].a+t<=a[r+1].t)
            f[l][r+1][a[r+1].a-a[l].a+t]=max(f[l][r+1][a[r+1].a-a[l].a+t],g[l][r][t]+a[r+1].b);
        }
        if (l>0) {
            g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]);
            g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]);
            if (a[r].a-a[l-1].a+t<=a[l-1].t)
            g[l-1][r][a[r].a-a[l-1].a+t]=max(g[l-1][r][a[r].a-a[l-1].a+t],f[l][r][t]+a[l-1].b);
            if (a[l].a-a[l-1].a+t<=a[l-1].t)
            g[l-1][r][a[l].a-a[l-1].a+t]=max(g[l-1][r][a[l].a-a[l-1].a+t],g[l][r][t]+a[l-1].b);
        }
    }
    int ans=0;
    for (int t=1;t<=mxt;t++)
    for (int l=bg;l>=0;l--)
    for (int r=bg;r<=m;r++)
    ans=max(ans,max(f[l][r][t],g[l][r][t]));
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
}