题目

题目描述

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 fA.(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

样例输入

3 2
0 1
1 0
4 3
1 2 3
1 2 3
1 2 3

样例输出

2
9

题意

  有n天，m件衣服，如果某一天穿了第i件衣服，第二天穿了第j件衣服，那么就会获得f[i][j]的权值。然后给你矩阵f，每件衣服可以穿无限多次，问第n天能获得的最大权值是多少。

思路

  设$dp[t][i][j]$为第1天穿第i件衣服第t天穿第j件衣服时能获得的最大的权值。假设$a + b = t$显然有$dp[t][i][j] = max_{1 \leq k \leq m}(dp[a][i][k] + dp[b][k][j])$，考虑矩阵快速幂。

实现

#include <bits/stdc++.h>
const int maxn = 107;
typedef long long ll;
ll max(ll a, ll b) { return a > b ? a : b; }
int n, m;
struct Matrix {
    ll data[maxn][maxn];
    Matrix operator * (const Matrix &tmp) const {
        Matrix ret;
        memset(ret.data, 0, sizeof(ret.data));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                for (int k = 1; k <= m; k++)
                    ret.data[i][j] = max(ret.data[i][j], data[i][k] + tmp.data[k][j]);
        return ret;
    }
} tmp;
Matrix qpow(Matrix p, int q) {
    Matrix ret;
    memset(ret.data, 0, sizeof(ret.data));
    for (; q; q >>= 1) {
        if (q & 1) ret = ret * p;
        p = p * p;
    }
    return ret;
}
ll solve() {
    Matrix result = qpow(tmp, n - 1);
    ll ans = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, result.data[i][j]);
    return ans;
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                scanf("%lld", tmp.data[i] + j);
        printf("%lld\n", solve());
    }
    return 0;
}