P8408 [COCI2009-2010#6] GREMLINI

· · 题解

其实本质上是一道 \text{dp} 题。

首先有如下事实：对于同代的同种小妖，我们只需考虑最早出生的那只。

原因：每只小妖的所有属性，包括成长时间，孵化种类及时间都是一定的。而我们要求的是最远到达的代数，所以只需考虑最早出生的那只即可。感性理解一下。

因此考虑动态规划。观察到 t 的范围较大，所以不妨使用倍增优化。那么状态该如何设计呢？首先应当存下每一种的最小孵化时间，因为 n\leq 100，所以不妨把这个单独作为一个数组存下来。那么此时根据倍增，以代数为阶段进行转移更新最小值，倍增的答案累加到 ans 中。

所以现在的目标就是如何较快地更新出每一种的最小值，为此我们可以预处理，令 d_{p,i,j} 表示经过 2^p 代，从 i 出生到 j 出生所需的最小时间，那么同样以倍增的形式进行转移，然后用类似 \texttt{Floyd} 的方式更新最短路。注意，因为这里的阶段是单独作为一维的，所以不用按照 \texttt{Floyd} 的方式在最外层枚举中转点的做法亦是可行的。然后更新答案的倍增倒序枚举，能更新就更新，根据二进制的相关知识，这样可以保证最优性。

时间复杂度 O(n^3\times \log t)。

#include<bits/stdc++.h>
#define N 105
using namespace std;
typedef long long ll;
int n,x[1005],y[1005];
ll T;
ll d[55][N][N];
ll now[N],mn[N];
int main()
{
    scanf("%d%lld",&n,&T);
    memset(d,0x3f,sizeof(d));
    for(int i=1;i<=n;i++)
    {
        int k,z;
        scanf("%d%d",&k,&z);
        for(int j=1;j<=k;j++) scanf("%d",&x[j]);
        for(int j=1;j<=k;j++) scanf("%d",&y[j]),d[0][i][x[j]]=min(d[0][i][x[j]],1ll*(z+y[j]));
    }
    for(int p=1;p<=50;p++)
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) d[p][i][j]=min(d[p][i][j],d[p-1][i][k]+d[p-1][k][j]);
    //d[p][i][j]表示从 i 到 j，繁殖(1<<p)代所需的最小年数 
    //不严格矩阵乘法，本质是倍增优化dp 
    ll ans=0;
    for(int p=50;p>=0;p--)
    { 
        for(int i=1;i<=n;i++) mn[i]=1e18;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mn[j]=min(mn[j],now[i]+d[p][i][j]);
        bool flag=0;
        for(int i=1;i<=n;i++) if(mn[i]<=T) flag=1;
        if(flag)
        {
            ans+=(1ll<<p);
            for(int i=1;i<=n;i++) now[i]=mn[i];
        }
    }
    printf("%lld\n",ans);
}