计算过程中会超 long long,试试高精或 int128
by ruanwentao666 @ 2023-10-21 19:23:47
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 85, Mod = 10000;
int n, m;
int ar[MAXN];
struct HP {
int p[505], len;
HP() {
memset(p, 0, sizeof p);
len = 0;
}
void print() {
printf("%d", p[len]);
for (int i = len - 1; i > 0; i--) {
if (p[i] == 0) {
printf("0000");
continue;
}
for (int k = 10; k * p[i] < Mod; k *= 10)
printf("0");
printf("%d", p[i]);
}
}
} f[MAXN][MAXN], base[MAXN], ans;
HP operator + (const HP &a, const HP &b) {
HP c; c.len = max(a.len, b.len); int x = 0;
for (int i = 1; i <= c.len; i++) {
c.p[i] = a.p[i] + b.p[i] + x;
x = c.p[i] / Mod;
c.p[i] %= Mod;
}
if (x > 0)
c.p[++c.len] = x;
return c;
}
HP operator * (const HP &a, const int &b) {
HP c; c.len = a.len; int x = 0;
for (int i = 1; i <= c.len; i++) {
c.p[i] = a.p[i] * b + x;
x = c.p[i] / Mod;
c.p[i] %= Mod;
}
while (x > 0)
c.p[++c.len] = x % Mod, x /= Mod;
return c;
}
HP max(const HP &a, const HP &b) {
if (a.len > b.len)
return a;
else if (a.len < b.len)
return b;
for (int i = a.len; i > 0; i--)
if (a.p[i] > b.p[i])
return a;
else if (a.p[i] < b.p[i])
return b;
return a;
}
void BaseTwo() {
base[0].p[1] = 1, base[0].len = 1;
for (int i = 1; i <= m + 2; i++){
base[i] = base[i - 1] * 2;
}
}
int main(void) {
scanf("%d%d", &n, &m);
BaseTwo();
while (n--) {
memset(f, 0, sizeof f);
for (int i = 1; i <= m; i++)
scanf("%d", &ar[i]);
for (int i = 1; i <= m; i++)
for (int j = m; j >= i; j--) {
f[i][j] = max(f[i][j], f[i - 1][j] + base[m - j + i - 1] * ar[i - 1]);
f[i][j] = max(f[i][j], f[i][j + 1] + base[m - j + i - 1] * ar[j + 1]);
}
HP Max;
for (int i = 1; i <= m; i++)
Max = max(Max, f[i][i] + base[m] * ar[i]);
ans = ans + Max;
}
ans.print();
return 0;
}
```
by akwbb @ 2023-10-27 08:03:04
@[akwbb](/user/1173153) 正确答案
by akwbb @ 2023-10-27 08:03:46
```cpp
#include <iostream>
#include <string>
#include <cstring>
#define _int __int128
using namespace std;
_int n,m,a[85][85],dp[85][85],s;
void read(_int &x){
string q;
cin>>q;
for (int i=0;i<q.size();i++){
x=x*10+(q[i]-'0');
}
}
void out(_int x){
if (x>9) out(x/10);
putchar(x%10+'0');
}
int main(){
read(n);read(m);
for (_int i=1;i<=n;i++){
for (_int j=1;j<=m;j++){
read(a[i][j]);
}
}
for (_int i=1;i<=n;i++){
for (_int j=0;j<=m;j++){
for (_int k=1;k+j<=m;k++){
dp[k][k+j]=max(2*dp[k+1][k+j]+2*a[i][k],2*dp[k][k+j-1]+2*a[i][k+j]);
}
}
s+=dp[1][m];
memset(dp,0,sizeof(dp));
}
out(s);
return 0;
}
```
by prg_equal_depressed @ 2023-10-27 18:28:41
已AC,谢谢 @[ruanwentao666](/user/782700) ,也谢谢 @[akwbb](/user/1173153) 大佬提供新思路,已关。
by prg_equal_depressed @ 2023-10-27 18:30:11
此贴结
by prg_equal_depressed @ 2023-10-27 18:30:43