忙碌了一个学期的 Q老师 决定奖励自己 N 天假期。
假期中不同的穿衣方式会有不同的快乐值。
已知 Q老师 一共有 M 件衬衫,且如果昨天穿的是衬衫 A,今天穿的是衬衫 B,则 Q老师 今天可以获得 f[A][B] 快乐值。
在 N 天假期结束后,Q老师 最多可以获得多少快乐值?
输入:
输入文件包含多组测试样例,每组测试样例格式描述如下:
第一行给出两个整数 N M,分别代表假期长度与 Q老师 的衬衫总数。(2 ≤ N ≤ 100000, 1 ≤ M ≤ 100)
接下来 M 行,每行给出 M 个整数,其中第 i 行的第 j 个整数,表示 f[i][j]。(1 ≤ f[i][j] ≤ 1000000)
测试样例组数不会超过 10。
输出:
每组测试样例输出一行,表示 Q老师 可以获得的最大快乐值。
样例输入:
3 2
0 1
1 0
4 3
1 2 3
1 2 3
1 2 3
样例输出:
2
9
f[i][j]表示第 i 天,穿的衣服为 j 所获得的快乐值总和。
这题最关键的是想到把累加替换为max,乘法替换为加法。
因为矩阵快速幂要求矩阵乘法具有结合律,而这样替换满足要求,所以可以用矩阵快速幂。
#include<iostream>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;
const int N=110;
int f[110][110];
int dp[110000][110];
struct Matrix{
ll x[N][N];
Matrix operator*(const Matrix& t)const
{
Matrix ret;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
for(int k=0;k<N;k++)
{
ret.x[i][j]=max(ret.x[i][j],x[i][k]+t.x[k][j]);
}
}
}
return ret;
}
Matrix()
{
memset(x,0,sizeof(x));
}
Matrix(const Matrix& t)
{
memcpy(x,t.x,sizeof(x));
}
};
Matrix quick_pow(Matrix a,int x)
{
Matrix ret;
memset(ret.x,0,sizeof(ret.x));
while(x)
{
if(x&1)
{
ret=ret*a;
}
a=a*a;
x>>=1;
}
return ret;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
cin>>f[i][j];
}
}
Matrix t1,t2;
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
t1.x[i][j]=f[i][j];
}
}
t2=quick_pow(t1,n-1);
ll ans=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
ans=max(ans,t2.x[i][j]);
}
}
cout<<ans<<endl;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)