题意：

有N天，一个人每天穿一件衣服，总共有m件衣服，某天穿颜色A下一天穿颜色B，能得到愉快值$f[A][B]$。问最大的愉快值是多少。

思路：

$dp[i][j][k]：第k天从i到j的最大愉快值$ ，

所以$dp[i][j][k]=max(dp[i][j][k],dp[i][t][k-1]+f[t][j])$。

这类似于矩阵乘法了，

矩阵乘法的形式为$dp[i][j][k]=dp[i][j][k]+dp[i][t][k-1]*f[t][j]$。

是很类似的。

这里注意初始化应该为全零矩阵而不是单位矩阵，因为初始的时候愉快值都为0。

max和加法本身都是可以交换和结合的，满足结合律的似乎都可以用矩阵做？

其实找个例子手算一下这种方法就有感觉了，挺妙的，以后对于这种松弛？的式子的时候可以考虑这种做法。

代码：

typedef long long ll;
int ss;
struct mat
{
    long long a[110][110];
}m,r;
mat mult(mat x,mat y)
{
    mat res={0};
    int i,j,k;
    for(i=0;i<ss;i++)
    for(j=0;j<ss;j++)
    for(k=0;k<ss;k++)
        res.a[i][j]=max(res.a[i][j],x.a[i][k]+y.a[k][j]);
    return res;
}
mat PowerMod(mat x,long long n)
{
    mat ans={0};
    int i,j;
    //for(i=0;i<ss;i++)
        //ans.a[i][i]=1;
    while(n>0)
    {
        if(n%2==1)ans=mult(ans,x);
        x=mult(x,x);
        n=n/2;
    }
    return ans;
}
int main()
{
    ll n;
    while(scanf("%lld%d",&n,&ss)!=EOF)
    {
        for(int i=0;i<ss;i++)
            for(int j=0;j<ss;j++)
            scanf("%lld",&m.a[i][j]);
        r=PowerMod(m,n-1);
        ll ans=0;
        for(int i=0;i<ss;i++)
            for(int j=0;j<ss;j++)
            ans=max(ans,r.a[i][j]);
        printf("%lld\n",ans);
    }
    return 0;
}