问题 I: T-shirt
时间限制: 1 Sec 内存限制: 64 MB提交: 14 解决: 7
[提交][状态][讨论版][命题人:admin]
题目描述
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.
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).
输出
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
提示
思路： 我的思路类似于最短路的floyd ， 对每天的每件物品求一下对m件衣服的权值和，保留一个最大值。
因为只需要选n-1天，所以用一个快速幂就可以了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
typedef long long ll;
ll n,m;
struct node{
ll f[maxn][maxn];
node(){
memset(f,0,sizeof(f));
}
node operator*(const node& p){
node ans;
for (int i=1; i<=m ;i++)
for (int j=1; j<=m ;j++)
for (int k=1; k<=m ;k++)
ans.f[i][j]=max(ans.f[i][j],f[i][k]+p.f[k][j]);
return ans;
}
node Pow_mod(ll n){
node ans;
node p=(*this);
while(n){
if(n&1) ans=ans*p;
p=p*p;
n>>=1;
}
return ans;
}
};
int main(){
while(scanf("%lld%lld",&n,&m)==2){
node mat;
for (int i=1; i<=m ;i++)
for (int j=1; j<=m; j++)
scanf("%lld",&mat.f[i][j]);
mat=mat.Pow_mod(n-1);
ll ans=0;
for (int i=1; i<=m ;i++)
for (int j=1; j<=m ;j++)
ans=max(ans,mat.f[i][j]);
printf("%lld
",ans);
}
return 0;
}