T-shirt

题目描述

JSZKC is going to spend his vacation!
His vacation has N days. Each day, he can choose a T-shirt to wear. Obviously, he doesn’t want to wear a singer color T-shirt since others will consider he has worn one T-shirt all the time.
To avoid this problem, he has M different T-shirt with different color. If he wears A color T-shirt this day and B color T-shirt the next day, then he will get the pleasure of f[A][B].(notice: He is able to wear one T-shirt in two continuous days but may get a low pleasure)
Please calculate the max pleasure he can get.

输入

The input file contains several test cases, each of them as described below.

The first line of the input contains two integers N,M (2 ≤ N≤ 100000, 1 ≤ M≤ 100), giving the length of vacation and the T-shirts that JSZKC has.
The next follows M lines with each line M integers. The jth integer in the ith line means f[i][j](1<=f[i][j]<=1000000).

There are no more than 10 test cases.

输出

One line per case, an integer indicates the answer

样例输入

样例输出

2
9

感觉蛮难的一道题，学长给我讲了还迷迷糊糊的，看了半小时才明白。
这题用的东西蛮多的，首先用了倍增的思想，f[i][j][k]表示走2^i次，从j->k的最大价值。也就是压缩了一下状态。
然后用了二进制的思想，把n分解成x1*2^p1+x2*2^p2+x3*2^p3.....xn*2^pn。 然后看能不能xi是否等于0，如果等于，可以走。 就进入递推，这样保证了一定走了n-1次。
然后用了一个状态压缩，因为每一步只和上一步有关，所以i只需要在0与1之间变化。

#include <bits/stdc++.h>
#define maxn 105
using namespace std;
typedef long long ll;
ll f[25][maxn][maxn]={0};
ll ans[2][maxn][maxn]={0};
int main()
{
    int n,m,i,j,k,l;
    while(~scanf("%d%d",&n,&m))
    {
        memset(f,0,sizeof(f));
        memset(ans,0,sizeof(ans));
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%lld",&f[0][i][j]);
            }
        }
        for(i=1;i<=20;i++)
        {
            for(j=1;j<=m;j++)
            {
                for(k=1;k<=m;k++)
                {
                    for(l=1;l<=m;l++)
                    {
                        f[i][j][k]=max(f[i][j][k],f[i-1][j][l]+f[i-1][l][k]);
                    }
                }
            }
        }
        n--;
        int temp=1;
        for(i=0;i<=20;i++)
        {
            if(n&(1<<i))
            {
                for(j=1;j<=m;j++)
            {
                for(k=1;k<=m;k++)
                {
                    for(l=1;l<=m;l++)
                    {
                        ans[temp][j][k]=max(ans[temp][j][k],ans[1-temp][j][l]+f[i][l][k]);
                    }
                }
            }
            temp=1-temp;
            }
        }
        temp=1-temp;
        ll maxim=0;
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=m;j++)
            {
                maxim=max(ans[temp][i][j],maxim);
            }
        }
        cout<<maxim<<endl;
    }
    return 0;
}