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 Bcolor 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.
Input Format
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 MM lines with each line MM integers. The j^{th}jth integer in the i^{th}ith line means [i][j] 1≤f[i][j]≤1000000).
There are no more than 1010 test cases.
Output Format
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
题目来源
The 2018 ACM-ICPC China JiangSu Provincial Programming Contest
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <string> 10 #include <cmath> 11 #include <cstdlib> 12 #include <ctime> 13 using namespace std; 14 typedef long long ll; 15 /* 16 f[a][b]+f[b][c]+f[c][d]+……+f[y][z]的最大值。(n-1项) 17 n=2 :二重循环 18 n=3 :三重循环 19 n=4 : f[a][b]+f[b][c]+f[c][d] 20 可以用f[a][c]来代替f[a][c]和f[a][b]+f[b][c]的较大值，在进行f[a][c]+f[c][d] 21 此时的f[a][c]表示第一天a,第三天c的最大值 22 n>=5的依此类推 23 那么可以利用矩阵快速幂的思想，因为(n-2)*m^2会超时 24 n=2要更新一次来找最大值,n=3就要更新2次。 25 因此n要更新n-1次。 26 */ 27 const int N=110; 28 ll f[N][N],n,m; 29 struct ma{ 30 ll m[N][N]; 31 ma(){ 32 memset(m,0,sizeof(m)); 33 } 34 }; 35 ll MAX; 36 ma poww(ma a,ma b) 37 { 38 ma c; 39 for(int i=0;i<m;i++) 40 { 41 for(int j=0;j<m;j++) 42 { 43 for(int k=0;k<m;k++) 44 { 45 c.m[i][j]=max(c.m[i][j],a.m[i][k]+b.m[k][j]); 46 } 47 } 48 } 49 return c; 50 } 51 ma qu(ma a,ll n){ 52 ma c; 53 while(n){ 54 if(n&1) c=poww(c,a); 55 n>>=1; 56 a=poww(a,a); 57 } 58 return c; 59 } 60 int main() 61 { 62 while(~scanf("%lld%lld",&n,&m)){ 63 ma ans; 64 for(int i=0;i<m;i++) 65 { 66 for(int j=0;j<m;j++) 67 { 68 scanf("%lld",&ans.m[i][j]); 69 } 70 } 71 ans=qu(ans,n-1); 72 MAX=0; 73 for(int i=0;i<m;i++){ 74 for(int j=0;j<m;j++) 75 { 76 MAX=max(MAX,ans.m[i][j]); 77 } 78 } 79 printf("%lld ",MAX); 80 } 81 return 0; 82 }