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