不充钱，你怎么AC？
题目：http://codevs.cn/problem/1166/
有许久没有刷题了，忙着过中秋去了嘿嘿
首先它的每一行是独立的，我们可以直接把它拆分成 n 互不相关的子问题做
那么就变成了区间 DP 问题，f[i][j] 表示在区间 [i,j] 内的最大分数，首先枚举区间长度 k，然后再枚举左端点 i
n 表示的是一行数的个数
注意 k 要到-1，是因为 f[i][i] 时还有一个 a[i] 没有取走，目标状态是 max ( f[i][i-1] ) ,（i=1~n）
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define N 90 8 using namespace std; 9 10 long long a[N],f[N][N],m,ans,t,n; 11 int main() 12 { 13 long long i,k; 14 cin>>t>>n; 15 while (t>0) 16 { 17 t--; 18 for (i=1;i<=n;i++) cin>>a[i]; 19 for (k=n-2;k>=-1;k--) 20 { 21 for (i=1;i<=n-k;i++) 22 { 23 f[i][i+k]=max(f[i-1][i+k]+a[i-1]*(1<<(n-k-1)),f[i][i+k+1]+a[i+k+1]*(1<<(n-k-1))); 24 } 25 } 26 m=0; 27 for (i=1;i<=n;i++) m=max(m,f[i][i-1]); 28 ans+=m; 29 } 30 cout<<ans<<endl; 31 return 0; 32 }
这段代码交上去只有60分，是为什么呢？
查了很久的问题，结果返回一看题目数据范围，要写高精度……当年应该觉得这道题太简单了，于是就放个高精度卡掉选手40分
那么就写一个高精度的加法和比较大小即可，直接贴别人的代码嘿嘿
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define maxn 100 5 #define base 10000 6 using namespace std; 7 8 int n,m,cnt=1,lp[85],rp[85]; 9 int map[85][85]; 10 struct Bign 11 { 12 int c[maxn],len; 13 Bign () 14 { 15 memset(c,0,sizeof(c)),len=1; 16 } 17 void Zero() 18 { 19 while(len>1&&c[len]==0)len--; 20 } 21 void Write(char *s) 22 { 23 int l=strlen(s); 24 int k=1; 25 for(int i=l-1;i>=0;i--) 26 { 27 c[len]+=k*(s[i]-'0'); 28 k*=10; 29 if(k==base) 30 { 31 k=1;len++; 32 } 33 } 34 } 35 void Read() 36 { 37 char s[maxn]; 38 scanf("%s",s); 39 Write(s); 40 } 41 void Print() 42 { 43 printf("%d",c[len]); 44 for(int i=len-1;i>=1;i--) printf("%04d",c[i]); 45 printf(" "); 46 } 47 Bign operator = (const int &a) 48 { 49 memset(c,0,sizeof(c)); 50 len=1; 51 char s[maxn]; 52 sprintf(s,"%d",a); 53 Write(s); 54 Zero(); 55 return *this; 56 } 57 Bign operator +(const Bign &a) 58 { 59 Bign r; 60 r.len=max(len,a.len)+1; 61 for(int i=1;i<=r.len;i++) 62 { 63 r.c[i]+=c[i]+a.c[i]; 64 r.c[i+1]+=r.c[i]/base; 65 r.c[i]%=base; 66 } 67 r.Zero(); 68 return r; 69 } 70 Bign operator +(const int &a) 71 { 72 Bign b; 73 b=a; 74 return *this+b; 75 } 76 Bign operator *(const Bign &a) 77 { 78 Bign r; 79 r.len=len+a.len+2; 80 for(int i=1;i<=len;i++) 81 { 82 for(int j=1;j<=a.len;j++) 83 { 84 r.c[i+j-1]+=c[i]*a.c[j]; 85 } 86 } 87 for(int i=1;i<=r.len;i++) 88 { 89 r.c[i+1]+=r.c[i]/base; 90 r.c[i]%=base; 91 } 92 r.Zero(); 93 return r; 94 } 95 Bign operator *(const int &a) 96 { 97 Bign b; 98 b=a; 99 return *this*b; 100 } 101 bool operator < (const Bign &b)const 102 { 103 if(len!=b.len) return len<b.len; 104 else 105 { 106 for(int i=len;i>=1;i--) 107 { 108 if(c[i]!=b.c[i]) return c[i]<b.c[i]; 109 } 110 } 111 return 0; 112 } 113 bool operator >(const Bign &b)const 114 { 115 return b<*this; 116 } 117 bool operator <=(const Bign &b)const 118 { 119 return !(b>*this); 120 } 121 bool operator >=(const Bign &b)const 122 { 123 return !(b<*this); 124 } 125 bool operator == (int a) 126 { 127 return len==1 && c[len]==a; 128 } 129 }; 130 Bign f[85][85]; 131 Bign Max(Bign a,Bign b) 132 { 133 if(a>=b) return a; 134 if(a<b) return b; 135 } 136 int main() 137 { 138 Bign ans; 139 ans=0; 140 scanf("%d%d",&n,&m); 141 for(int i=1;i<=n;i++) 142 { 143 for(int j=1;j<=m;j++) 144 { 145 scanf("%d",&map[i][j]); 146 } 147 } 148 for (int i=1;i<=n;i++) 149 { 150 for(int u=1;u<=m;u++) 151 for(int v=1;v<=m;v++) f[v][u]=0; 152 for (int j=1;j<=m;j++) 153 { 154 f[j][j]=map[i][j]*2; 155 } 156 for(int len=1;len<=m-1;len++) 157 { 158 for(int l=1;l<=m&&l+len<=m;l++) 159 { 160 Bign k; 161 k=max(f[l+1][l+len]+map[i][l],f[l][l+len-1]+map[i][l+len]); 162 f[l][l+len]=k*2; 163 } 164 } 165 ans=ans+f[1][m]; 166 } 167 ans.Print() ; 168 return 0 ; 169 }