题目链接：https://ac.nowcoder.com/acm/contest/3004/J
题目大意：


我们可以很容易得到一个K^2的算法。因为每个时间都不同。那么按时间排序。就是一个LIS。如果满足(j->i)时间差>=dis(i, j)那么就可以转移。
f [ i ] : 在 捉 完 第 i 只 宝 可 梦 获 得 的 最 大 战 斗 力 f[i]:在捉完第i只宝可梦获得的最大战斗力 f[i]:在捉完第i只宝可梦获得的最大战斗力
f [ i ] = m a x ( f [ i ] ， f [ j ] + a [ i ] . v ) j < i , a [ i ] . t − a [ j ] . t > = d i s ( i , j ) f[i]=max(f[i]，f[j]+a[i].v) \quad j<i,a[i].t-a[j].t>=dis(i, j) f[i]=max(f[i]，f[j]+a[i].v)j<i,a[i].t−a[j].t>=dis(i,j)
这里k太大。k^2肯定是不可以的。但是如果：
a [ i ] . t − a [ j ] . t > = 200 。 那 么 f [ i ] = m a x ( f [ i ] , f [ j ] ) a[i].t-a[j].t>=200。那么f[i]=max(f[i], f[j]) a[i].t−a[j].t>=200。那么f[i]=max(f[i],f[j])
因为：这个时候一定满足 a [ i ] . t − a [ j ] . t > = d i s ( i , j ) a[i].t-a[j].t>=dis(i, j) a[i].t−a[j].t>=dis(i,j)
最多200个点。那么 d i s ( i , j ) < = 200 dis(i, j)<=200 dis(i,j)<=200
所以转移方程：
{ <mstyle displaystyle="false" scriptlevel="0"> f [ i ] = m a x ( f [ i ] ， f [ j ] + a [ i ] . v ) </mstyle> <mstyle displaystyle="false" scriptlevel="0"> <mtext> j>i-200,a[i].t-a[j].t>=dis(i, j)  </mtext> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> f [ i ] = m a x ( f [ i ] ， f [ j ] + a [ i ] . v ) </mstyle> <mstyle displaystyle="false" scriptlevel="0"> <mtext> j<i-200 </mtext> </mstyle> \begin{cases} f[i]=max(f[i]，f[j]+a[i].v) & \text{j>i-200,a[i].t-a[j].t>=dis(i, j) } \\ f[i]=max(f[i]，f[j]+a[i].v) & \text{j<i-200} \end{cases} {f[i]=max(f[i]，f[j]+a[i].v)f[i]=max(f[i]，f[j]+a[i].v)​j>i-200,a[i].t-a[j].t>=dis(i, j) j<i-200​
第一部分暴力转移。第二部分前缀最大值。所以复杂度为O(200*k)。

注意要把f[]的初始值设-1.表示这个状态不能到达。并不是每个宝可梦都是可以捉到的。例如：
3
1 2
2 3
1
1 3

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=205;

LL n, m;
LL e[maxn][maxn];
LL f[100005];
struct node{
    LL t, p;
    LL v;
}a[100005];

int cmp(node &a, node &b){
    return a.t<b.t;
}

void floyd(){
    for(LL k=1;k<=n;k++){
        for(LL i=1;i<=n;i++){
            for(LL j=1;j<=n;j++){
                e[i][j]=min(e[i][j], e[i][k]+e[k][j]);
            }
        }
    }
}

int main()
{
    LL k, x, y, z;
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) e[i][j]=0;
            else e[i][j]=(1ll<<60);
        }
    }
    for(LL i=1;i<=m;i++){
        scanf("%lld%lld",&x,&y);
        e[x][y]=e[y][x]=1;
    }
    floyd();
    scanf("%lld", &k);
    for(LL i=1; i<=k; i++){
        scanf("%lld%lld%lld", &a[i].t, &a[i].p, &a[i].v);
    }
    sort(a+1, a+k+1, cmp);
    memset(f, -1,sizeof(f));
    a[0].p=1; f[0]=0;
    LL Max=0;
    for(LL i=1; i<=k; i++){
        for(LL j=1; j<200&&j<=k; j++){
            if(i-j>=0&&a[i].t-a[i-j].t>=e[a[i].p][a[i-j].p]&&f[i-j]!=-1){//f[i-j]!=-1 f[i-j]这个状态一定存在
                f[i]=max(f[i], f[i-j]+a[i].v);
            }
        }
        if(i>=200){
            f[i]=max(f[i], f[i-200]+a[i].v);
            f[i-199]=max(f[i-200], f[i-199]);
        }
        Max=max(Max, f[i]);
    }
    printf("%lld\n", Max);

    return 0;
}