十年以前，提高组的题目居然要写高精度！！！！
这不是摆明了刁难人吗！！！！！！！
Analysis
你需要写的高精度：
- 高精度加法
- 高精度比较大小
- 高精度乘高精度
- 高精度乘低精度
- 高精度赋初值
虽然这一道题目是一道$dp$，但是高精度完全抢走了所有的风头
关于着一道题目的$dp$，首先，就是在于每一行都是独立的，互相影响，所以说每一行单独来$dp$就可以了。
我们设$f[i][j]$来表示$[i,j]$区间里面的最优情况，他可能是是从$[i+1,j]$和$[i,j-1]$两种情况推过来的，所以说因此就可以得出他的方程了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| #include<bits/stdc++.h>
#define maxn 85
#define carry 1000
using namespace std;
int N,M;
int matrix[maxn][maxn];
struct Largenum{
int val[maxn];
int operator [](const int &ref)const{
return val[ref];
}
Largenum(int a){
memset(val,0,sizeof(val));
int pos=1;
while(a){
val[pos]=a%carry;
a/=carry;
pos++;
}
val[0]=pos;
}
Largenum(void){
memset(val,0,sizeof(val));
}
inline void output(){
printf("%d",val[val[0]]);
for(int i=val[0]-1;i>=1;i--)
printf("%03d",val[i]);
}
Largenum operator +(const Largenum &obj)const{
Largenum cmp;
int add=0,pos=max(val[0],obj.val[0]);
for(int i=1;i<=pos;i++){
cmp.val[i]=obj.val[i]+val[i]+add;
add=cmp.val[i]/carry;
cmp.val[i]%=carry;
}
if(add>0)cmp.val[++pos]=add;
cmp.val[0]=pos;
return cmp;
}
bool operator ==(const Largenum &obj)const{
if(val[0]!=obj[0])return false;
for(int i=1;i<=val[0];i++)if(val[i]!=obj[i])return false;
return true;
}
bool operator <(const Largenum &obj)const{
if(val[0]>obj[0])return false;
if((*this)==obj)return false;
if(val[0]<obj[0])return true;
for(int i=val[0];i>=1;i--){
if(val[i]>obj[i])return false;
if(val[i]<obj[i])return true;
}
return true;
}
Largenum operator *(const Largenum &obj)const{
Largenum cmp;
int pos=val[0]+obj[0];
for(int i=1;i<=val[0];i++){
for(int j=1;j<=obj[0];j++){
cmp.val[i+j-1]+=val[i]*obj[j];
cmp.val[i+j]+=cmp.val[i+j-1]/carry;
cmp.val[i+j-1]=cmp.val[i+j-1]%carry;
}
}
while(cmp.val[pos]==0&&pos>1)pos--;
cmp.val[0]=pos;
return cmp;
}
Largenum operator *(const int &obj)const{
Largenum cmp;
int pos=val[0];int add=0;
for(int i=1;i<=pos;i++){
cmp.val[i]=val[i]*obj+add;
add=cmp.val[i]/carry;
cmp.val[i]=cmp.val[i]%carry;
}
while(add>0){
cmp.val[++pos]=add%carry;
add/=carry;
}
while(cmp.val[pos]==0&&pos>1)pos--;
cmp.val[0]=pos;
return cmp;
}
}two[maxn],f[maxn][maxn],ans(0);
void init(int M){
two[0]=Largenum(1);
for(int i=1;i<=M;i++)
two[i]=two[i-1]*2;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
scanf("%d",&matrix[i][j]);
init(M);
for(int k=1;k<=N;k++){
memset(f,0,sizeof(f));
for(int t=0;t<M;t++){
for(int i=1;i+t<=M;++i){
int j=i+t;
int pw=M-t;
Largenum fir=(f[i+1][j]+two[pw]*matrix[k][i]);
Largenum sec=(f[i][j-1]+two[pw]*matrix[k][j]);
if(fir<sec)f[i][j]=sec;
else f[i][j]=fir;
}
ans=ans+f[1][M];
}
}
ans.output();
return 0;
}
|