自动搬运

查看原文

来自洛谷，原作者为

	Utilokasteinn 技不如人

搬运于2025-08-24 22:21:29，当前版本为作者最后更新于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;
}