AT_kupc2013_f ７歳教 题解

· · 题解

O(N^3)

既然题目对所经过的城市没有要求，所以可以跑一遍最短路。考虑到城市数量较少，使用 Floyd算法 ，时间复杂度为 O(N^3) ,现在我们只需要考虑如何遍历以得分最大。

小结论：在一个城市要么路过，要么一直待到该城市的加分时间截止。

如果我来到这个城市的时间在加分时间段之后，那么我必然去别的城市。（路过）

如果我现在在这个城市时可以加分，那我为什么要去别的地方呢，因为每天不论在哪个城市加的分是一样的。（就像一个人有两个地方可以打零工，他现在在一处上班，肯定不会再花时间去另一个地方，不光路上要花时间，到那边开不开门也另说）

考虑到这个结论，我们除去路过的城市，肯定是先去截止时间早的城市加分，再去截止时间晚的城市加分。

所以我们可以按照截止时间排序，在考虑从截止时间早的城市走来就行了，时间复杂度为 O(N^2) 。

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    long long l,r,id;
};
node a[503];
long long v[503][503];
long long f[503];//表示目前到 i 这个节点的最大积分 
long long n,st,ti,maxx,from,to,maxxxx=1ll<<60;
bool cmp(node x,node y)
{
    return x.r<y.r;
}
int main()
{
    scanf("%lld%lld",&n,&st);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].l,&a[i].r),a[i].id=i,f[i]=-maxxxx;//初始化 
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&v[i][j]);
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) v[i][j]=min(v[i][k]+v[k][j],v[i][j]);//Floyd 
    sort(a+1,a+1+n,cmp); 
    f[st]=0;
    for(int i=1;i<=n;i++)
    {
        to=a[i].id;//截止时间晚的城市 
        for(int j=1;j<i;j++)
        {
            from=a[j].id;//截止时间早的城市 
            ti=max(a[j].r+v[from][to],a[i].l);//从到达这一城市或这一城市开始时间算 
            if(a[i].r>=ti) f[to]=max(f[to],f[from]+a[i].r-ti);//状态转移 
        }
        ti=max(v[st][to],a[i].l);//从起点走来 
        if(a[i].r>=ti) f[to]=max(f[to],a[i].r-ti);//状态转移 
    }
    for(int i=1;i<=n;i++) maxx=max(maxx,f[i]);
    printf("%lld\n",maxx);
}