华师一附中OI组

标题: P1005 矩阵取数游戏 [打印本页]
作者: admin    时间: 2018-7-4 23:39
标题: P1005 矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 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    时间: 2018-7-22 12:02
区间DP的经典例子，转移方程如何写是一方面，还有一个是涉及高精度计算，如何做最高效呢？ NOIP考题其实都不难，但是要考察知识掌握的熟练程度！
作者: 吴语林    时间: 2018-7-29 19:43
  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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-10-2 15:47
本帖最后由 倚窗倾听风吹雨 于 2018-10-2 15:49 编辑

打高精做法。毕竟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. }
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2