zoj2901【DP·二进制优化】

题意：

要排一个L长度的序列，当 j 放在 i 后面的时候会增加v[ i ][ j ]的值，求构成L长度序列的最大值。

思路：

可以想到预处理任意两点<i,j>的最大值是多少，然后题目还有个限制，就是长度，那么再加一维k，

DP[k][i][j] 代表长度为k，i 到 j的最大价值。

但是我们看到L很大，这样不行，那么就把长度表示成二进制，dp[0][i][j]为长度为1时，i到j的最大价值，dp[k][i][j]代表长度为(2^k+1)，i到j的最大价值。

最后求长度L的最大值。

贴一发大神的code。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const int N=1e2+10;

LL f[20][N][N],g[2][N];
int n,L;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&L);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%lld",&f[0][i][j]);

        --L;

        int lev=0;
        for(int i=0;(1<<(i+1))<=L;i++)
        {
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                {
                        f[i+1][j][k]=-INF;
                        for(int x=0;x<n;++x)
                            f[i+1][j][k]=max(f[i][j][x]+f[i][x][k],f[i+1][j][k]);
                }
            ++lev;
        }
        int cur=0;
        fill(g[cur],g[cur]+n,0);
        for(int i=lev;i>=0;--i)
        {
            if(L<(1<<i)) continue;
            L-=(1<<i);
            cur=1-cur;
            fill(g[cur],g[cur]+n,-INF);
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                g[cur][k]=max(g[1-cur][j]+f[i][j][k],g[cur][k]);
        }
        printf("%lld\n",*max_element(g[cur],g[cur]+n));
    }
    return 0;
}


           

转载于:https://www.cnblogs.com/keyboarder-zsq/p/6777406.html