高精度应该没有问题,问题应该在于DP部分。如果DP部分没有问题也可以说一声,让我再检查一遍高精度。如果方便的话,随便看看高精度部分呗!谢谢大佬们的指点啦!
#include<iostream>
#include<cstdio>
#include<deque>
using std::deque;
const int js = 1e8, w = 8;
class sum {//高精度封装(8至192行)
public:
deque<unsigned long> s{ 0 };
unsigned la = 0, ls = 0;
sum(unsigned long n) :s{n} {}
sum(sum& a) :s{ a.s } {};
sum() = default;
sum operator + (const sum& a)
{
la = a.s.size();
ls = s.size();
sum b; b.s = s;
if (ls < la)
{
for (; ls <= la; ++ls)
b.s.push_front(0);
}
for (int i = la - 1, j = ls - 1; i >= 0; --i, --j)
b.s[j] += a.s[i];
for (int i = ls - 1; i > 0; --i)
{
b.s[i - 1] += b.s[i] / js;
b.s[i] %= js;
}
if (b.s[0] >= js)
{
b.s.push_front(b.s[0] / js);
b.s[1] %= js;
}
while (!b.s.empty()&&b.s[0] == 0) b.s.erase(b.s.begin());
return b;
}
sum operator + (const int& a)
{
sum b;
ls = s.size();
b.s = s;
b.s.back() += a;
for (int i = ls - 1; i > 0; --i)
{
b.s[i - 1] += b.s[i] / js;
b.s[i] %= js;
}
if (b.s[0] >= js)
{
b.s.push_front(b.s[0] / js);
b.s[1] %= js;
}
return b;
}
sum& operator += (const sum& a)
{
la = a.s.size();
ls = s.size();
if (ls < la)
{
for (; ls <= la; ++ls)
s.push_front(0);
}
for (int i = la - 1, j = ls - 1; i >= 0; --i, --j)
s[j] += a.s[i];
for (int i = ls - 1; i > 0; --i)
{
s[i - 1] += s[i] / js;
s[i] %= js;
}
if (s[0] >= js)
{
s.push_front(s[0] / js);
s[1] %= js;
}
while (!s.empty()&&s[0] == 0) s.erase(s.begin());
return *this;
}
sum operator * (const int& n)
{
ls = s.size();
sum a;
a.s = s;
for (int i = 0; i < ls; ++i)
{
a.s[i] *= n;
}
for (int i = ls - 1; i > 0; --i)
{
a.s[i - 1] += a.s[i] / js;
a.s[i] %= js;
}
if (a.s[0] >= js)
{
a.s.push_front(a.s[0] / js);
a.s[1] %= js;
}
return a;
}
sum& operator *= (const int& n)
{
ls = s.size();
for (int i = 0; i < ls; ++i)
{
s[i] *= n;
}
for (int i = ls - 1; i > 0; --i)
{
s[i - 1] += s[i] / js;
s[i] %= js;
}
if (s[0] >= js)
{
s.push_front(s[0] / js);
s[1] %= js;
}
return *this;
}
void operator = (const sum& a)
{
s = a.s;
return;
}
void operator = (int& n)
{
s.erase(s.begin(), s.end());
s.push_front(n);
return;
}
bool operator >= (const sum& a)
{
ls = s.size();
la = a.s.size();
if (ls > la) return true;
if (ls < la) return false;
for (int i = 0; i < ls; ++i)
if (s[i] < a.s[i])
return false;
return true;
}
bool operator <= (const sum& a)
{
ls = s.size();
la = a.s.size();
if (ls < la) return true;
if (ls > la) return false;
for (int i = 0; i < ls; ++i)
if (s[i] > a.s[i])
return false;
return true;
}
bool operator > (const sum& a)
{
ls = s.size();
la = a.s.size();
if (ls > la) return true;
if (ls < la) return false;
if (s == a.s) return false;
for (int i = 0; i < ls; ++i)
if (s[i] < a.s[i])
return false;
return true;
}
bool operator < (const sum& a)
{
ls = s.size();
la = a.s.size();
if (ls > la) return false;
if (ls < la) return true;
return s < a.s;
}
friend void print(sum& a);
};
void print(sum& a);//用于输出结果。
sum ans, dp[80][80],a,b;
unsigned int n, m,jz[80][80],sj,j;
unsigned long h;
int main()
{
scanf("%d %d", &n, &m);//输入部分。
for(int i=0;i<n;++i)
for (j=0; j < m; ++j)
scanf("%d", jz[i] + j);
//DP部分。采用的是从小区间到大区间的思想。
for (int k = 0; k < n; ++k)
{
for (int i = 0; i < m; ++i)
{
dp[i][i] = jz[k][i] * 2;
}
for (int len = 2; len <= m; ++len)
{
sj = m - len + 1;
for (int i = 0; i < sj; ++i)
{
j = i + len - 1;
a = dp[i][j - 1] + jz[k][j];
b = dp[i+1][j] + jz[k][i];
if (a > b)
dp[i][j] = a;
else dp[i][j] = b;
dp[i][j] *= 2;
}
}
if(m)
ans += dp[0][m-1];
}
print(ans);
}
void print(sum& a)
{
h = a.s[0];
printf("%ld", h);
n = a.s.size();
for (int i = 1; i < n; ++i)
{
h = a.s[i];
printf("%0*ld", w, h);
}
return;
}