题解 P6512 【[QkOI#R1] Quark and Flying Pigs】

Utilokasteinn · 2020-05-04 20:07:21 · 题解

P6512 [QkOI#R1] Quark and Flying Pigs

简单 DP。

设 dis_{u,v} 表示从 u 到 v 的最短路径，这可以用 Floyd 在 \mathcal{O}(n^3) 的复杂度内预处理出。

对于第 i 只飞猪和第 j 只飞猪，因为可以在一个点上停留，容易发现若 t_i+dis_{pos_i,pos_j}\le t_j，那么人就可以在抓到 i 之后到 j 的位置去抓 j。

那么就容易想到 DP。

设 f_i 表示抓住第 i 只飞猪的前提下，前 i 只飞猪最多可以抓几只。

那么转移方程便容易写出，枚举 j（j<i），看是否可以从 j 到 i，来更新答案。

具体转移方程见代码，代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        s=s*10+c-'0';
    return s;
}
int n,m,s;
int dis[205][205],f[5005],ans;
struct node
{
    int t,pos;
}a[5001];
bool cmp(node x,node y){return x.t<y.t;}
int main()
{
    n=read(),m=read(),s=read();
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        dis[u][v]=dis[v][u]=w;
    }
    for(int i=1;i<=n;i++)
        dis[i][i]=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=s;i++)
        a[i].t=read(),a[i].pos=read();
    sort(a+1,a+s+1,cmp);
    a[0].pos=1;//时刻为0的时候，人在位置1
    for(int i=1;i<=s;i++)
        for(int j=0;j<i;j++)
            if(dis[a[i].pos][a[j].pos]+a[j].t<=a[i].t)
                f[i]=max(f[i],f[j]+1);
    for(int i=1;i<=s;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}