P1005 矩阵取数游戏

admin

题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n×m 的矩阵，矩阵中的每个元素 ai,j均为非负整数。游戏规则如下：

每次取数时须从每行各取走一个元素，共 n个。经过 m 次后取完矩阵内所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 ×2^i  ，其中 i 表示第 i 次取数（从 1 开始编号）；
游戏结束总得分为 m 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入输出格式
输入格式：
输入文件包括 n+1 行：

第 1行为两个用空格隔开的整数 n 和 m 。

第 2~n+1 行为n×m 矩阵，其中每行有 m 个用单个空格隔开的非负整数。

输出格式：
输出文件仅包含 1行，为一个整数，即输入矩阵取数后的最大得分。

输入输出样例
输入样例#1：
2 3
1 2 3
3 4 2
输出样例#1：
82
说明
NOIP 2007 提高第三题

数据范围：

60%的数据满足：1≤n,m≤30 ，答案不超过 10^16

100%的数据满足： 1≤n,m≤80 ，ai,j≤1000

admin

区间DP的经典例子，转移方程如何写是一方面，还有一个是涉及高精度计算，如何做最高效呢？ NOIP考题其实都不难，但是要考察知识掌握的熟练程度！

吴语林

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <set>
   
7. using namespace std;
   
8. typedef __int128 u128;
   
9. u128 ans,f[85][85]={0};
   
10. int a[85][85]={0},*b,n,m;
    
11. void print(u128 p)
    
12. {
    
13.         if(p) print(p/10), putchar(p%10+'0');
    
14. }
    
15. int main()
    
16. {
    
17.         scanf("%d%d",&n,&m);
    
18.         for(int i=1;i<=n;i++)
    
19.                 for(int j=1;j<=m;j++)
    
20.                         scanf("%d",&a[i][j]);
    
21.         for(int h=1;h<=n;h++)
    
22.         {
    
23.                 b=a[h];
    
24.                 for(int i=0;i<=m;i++)
    
25.                         for(int j=0;j<=m;j++)
    
26.                                 f[i][j]=0;
    
27.                 u128 p=1;
    
28.                 for(int l=m-1;l>=0;l--)
    
29.                 {
    
30.                         p+=p;
    
31.                         for(int i=1;i+l<=m;i++)
    
32.                         {
    
33.                                 int j=i+l;
    
34.                                 f[i][j-1]=max(f[i][j-1],f[i][j]+p*b[j]);
    
35.                                 f[i+1][j]=max(f[i+1][j],f[i][j]+p*b[i]);
    
36.                         }
    
37.                 }
    
38.                 u128 res=0;
    
39.                 for(int i=1;i<=m;i++)
    
40.                         res=max(res,f[i][i-1]);
    
41.                 ans+=res;
    
42.         }
    
43.         if(ans) print(ans), putchar('\n');
    
44.         else puts("0");
    
45.         return 0;
    
46. }

复制代码

倚窗倾听风吹雨

打高精做法。毕竟noip不让用__int128,调了一个中午，难受。

1. #include<iostream>
   
2. #include<cstring>
   
3. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
4. #define ROF(i,a,b) for(int i=a;i>=b;i--)
   
5. using namespace std;
   
6. const int M=100;
   
7. int n,m,jz[M][M][M],f[M][M][M],er[M][M],ans[M],A[M],B[M],c[M];
   
8. string s;
   
9. inline void mul(int *a,int *b)
   
10. {
    
11.     memset(c,0,sizeof(c));
    
12.     int ex;
    
13.     FOR(i,1,a[0])
    
14.     {
    
15.         ex=0;
    
16.         FOR(j,1,b[0])
    
17.         {
    
18.             c[i+j-1]+=(a[i]*b[j]+ex);
    
19.             ex=c[i+j-1]/10;
    
20.             c[i+j-1]%=10;
    
21.         }
    
22.         c[i+b[0]]=ex;
    
23.     }
    
24.     c[0]=a[0]+b[0];
    
25.     while(c[0]>1 && !c[c[0]])c[0]--;
    
26.     FOR(i,0,c[0])a[i]=c[i];
    
27.     return;
    
28. }
    
29. inline void add(int *a,int *b)
    
30. {
    
31.     memset(c,0,sizeof(c));
    
32.     c[0]=max(a[0],b[0]);
    
33.     FOR(i,1,c[0])
    
34.     {
    
35.         c[i]+=a[i]+b[i];
    
36.         c[i+1]+=c[i]/10;
    
37.         c[i]%=10;
    
38.     }
    
39.     c[0]++;
    
40.     while(!c[c[0]] && c[0]>1)c[0]--;
    
41.     FOR(i,0,c[0])a[i]=c[i];
    
42.     return;
    
43. }
    
44. inline bool Max(int *a,int *b)
    
45. {
    
46.     while(a[0]>0 && !a[a[0]])a[0]--;
    
47.     while(b[0]>0 && !b[b[0]])b[0]--;
    
48.     if(a[0]!=b[0])return a[0]>b[0];
    
49.     ROF(i,a[0],1)if(a[i]!=b[i])return a[i]>b[i];
    
50.     return true;
    
51. }
    
52. inline void print(int *a)
    
53. {
    
54.     while(a[0]>1 && a[a[0]]==0)a[0]--;
    
55.     ROF(i,a[0],1)cout<<a[i];
    
56.     cout<<endl;
    
57. }
    
58. int main()
    
59. {
    
60.     cin>>n>>m;
    
61.     FOR(i,1,n)FOR(j,1,m)
    
62.     {
    
63.         cin>>s;
    
64.         ROF(k,s.size()-1,0)
    
65.           jz[i][j][++jz[i][j][0]]=s[k]-'0';
    
66.     }
    
67.     er[0][0]=1;er[0][1]=1;
    
68.     FOR(i,1,m)
    
69.     {
    
70.         FOR(j,0,er[i-1][0])er[i][j]=er[i-1][j];
    
71.         add(er[i],er[i-1]);
    
72.         ///print(er[i]);
    
73.     }
    
74.     FOR(i,1,n)
    
75.     {
    
76.         memset(f,0,sizeof(f));
    
77.         FOR(j,1,m)
    
78.         {
    
79.             add(f[j][j],jz[i][j]);
    
80.             ///print(f[j][j]);
    
81.             mul(f[j][j],er[m]);
    
82.             ///print(f[j][j]);
    
83.         }
    
84.         FOR(l,1,m-1)
    
85.         for(int j=1,k=j+l;k<=m;j++,k++)
    
86.         {
    
87.             memset(A,0,sizeof(A));
    
88.             add(A,jz[i][j]);
    
89.             mul(A,er[m-l]);
    
90.             add(A,f[j+1][k]);
    
91.             memset(B,0,sizeof(B));
    
92.             add(B,jz[i][k]);
    
93.             mul(B,er[m-l]);
    
94.             add(B,f[j][k-1]);
    
95.             ///print(A);print(B);
    
96.             if(Max(A,B))FOR(o,0,A[0])f[j][k][o]=A[o];
    
97.             else FOR(o,0,B[0])f[j][k][o]=B[o];
    
98.         }
    
99.         ///print(f[1][m]);
    
100.         add(ans,f[1][m]);
     
101.     }
     
102.     print(ans);
     
103.     return 0;
     
104. }
     

复制代码