洛谷P1005 矩阵取数游戏 DP+高精类

  1 #include<cstdio>
  2 #include<cstring>
  3 
  4 using namespace std;
  5 
  6 inline int max(int x,int y){
  7     if(x>y)return x;else return y;
  8 }
  9 
 10 struct bignum{
 11     int c[10],l;
 12     
 13     void clear(){
 14         memset(c,0,sizeof(c));
 15         l=1;
 16     }
 17     
 18     bignum(){
 19         clear();
 20     }
 21     
 22     bignum operator =(int x){
 23         memset(c,0,sizeof(c));
 24         l=0;
 25         while(x){
 26             l++;
 27             c[l]=x%10000;
 28             x/=10000;
 29         }
 30         return *this;
 31     }
 32     
 33     bignum(int x){
 34         *this=x;
 35     }
 36     
 37     void print(){
 38         printf("%d",c[l]);
 39         for(int i=l-1;i>=1;i--){
 40             if(c[i]<10)printf("000");
 41             else if(c[i]<100)printf("00");
 42             else if(c[i]<1000)printf("0");
 43             printf("%d",c[i]);
 44         }
 45     }
 46 };
 47 
 48 bignum operator +(bignum a,bignum b){
 49     bignum ans;
 50     ans.l=max(a.l,b.l); 
 51     for(int i=1;i<=ans.l;i++)ans.c[i]=a.c[i]+b.c[i];
 52     for(int i=1;i<=ans.l;i++)
 53         if(ans.c[i]>=10000){
 54             ans.c[i]-=10000;
 55             ans.c[i+1]++;
 56         }
 57     if(ans.c[ans.l+1])ans.l++;
 58     return ans;
 59 }
 60 
 61 bignum operator *(bignum a,bignum b){
 62     bignum ans;
 63     for(int i=1;i<=a.l;i++)
 64         for(int j=1;j<=b.l;j++){
 65             ans.c[i+j-1]+=a.c[i]*b.c[j];
 66             ans.c[i+j]+=ans.c[i+j-1]/10000;
 67             ans.c[i+j-1]%=10000;
 68         }
 69     if(ans.c[a.l+b.l])ans.l=a.l+b.l;else ans.l=a.l+b.l-1;
 70     return ans;
 71 }
 72 
 73 bool operator <(bignum a,bignum b){
 74     if(a.l!=b.l)return a.l<b.l;
 75     for(int i=a.l;i>=1;i--)if(a.c[i]!=b.c[i])return a.c[i]<b.c[i];
 76     return 0;
 77 }
 78 
 79 bool operator >(bignum a,bignum b){
 80     return b<a;
 81 }
 82 
 83 bignum dfs(int,int);
 84 
 85 int n,m;
 86 int c[82];
 87 bignum f[82][82];
 88 bool pd[82][82];  //0表示未使用 
 89 bignum ans;
 90 bignum fz[82];
 91 
 92 int main(){
 93     scanf("%d%d",&n,&m);
 94     fz[1]=2;
 95     for(int i=2;i<=m;i++)fz[i]=fz[i-1]*bignum(2);
 96     for(int i=1;i<=n;i++){
 97         for(int j=1;j<=m;j++)scanf("%d",&c[j]);
 98         memset(pd,0,sizeof(pd));
 99         ans=ans+dfs(1,m);
100     }
101     ans.print();
102     printf("
");
103     
104     return 0;
105 }
106 
107 bignum dfs(int l,int r){  //边界判断置于上一层,进入函数的l,r合法 
108      if(pd[l][r])return f[l][r];
109      pd[l][r]=1;
110      if(l==r)return f[l][r]=bignum(c[l])*fz[m];
111      bignum ans1=bignum(c[l])*fz[m-(r-l)]+dfs(l+1,r);
112      bignum ans2=bignum(c[r])*fz[m-(r-l)]+dfs(l,r-1);
113      if(ans2<ans1)return f[l][r]=ans1;
114      else return f[l][r]=ans2;
115 }