全班都进前50的屑 • 2年前
int a[MAXN], f[MAXN][MAXN][MAXLEN], ans[MAXLEN], tem1[MAXLEN], tem2[MAXLEN]; int from[MAXN][MAXN]; int n, m;
int cmp(int a[], int b[]) {
int l1 = a[0], l2 = b[0];
if (l1 > l2)
return 1;
if (l1 < l2)
return -1;
for (int i = l1; i > 0; --i)
if (a[i] > b[i])
return 1;
else if (a[i] < b[i])
return -1;
return 0;
}
void plus(int a[], int b) {
a[1] += b;
for (int i = 1; i < MAXLEN; ++i) {
a[i + 1] += a[i] / BASE;
a[i] %= BASE;
}
for (int i = MAXLEN - 1; i > 0; --i)
if (a[i]) {
a[0] = i;
break;
}
if (!a[0])
a[0] = 1;
}
void s_plus(int a[], int b[]) {
int c[MAXLEN];
memset(c, 0, sizeof(c));
for (int i = 1; i < MAXLEN; ++i) {
c[i] += a[i] + b[i];
c[i + 1] = c[i] / BASE;
c[i] %= BASE;
}
for (int i = MAXLEN - 1; i > 0; --i)
if (c[i]) {
c[0] = i;
break;
}
for (int i = 0; i < MAXLEN; ++i)
a[i] = c[i];
}
void cheng(int a[]) {
for (int i = 1; i < MAXLEN; ++i)
a[i] *= 2;
for (int i = 1; i < MAXLEN; ++i) {
a[i + 1] += a[i] / BASE;
a[i] %= BASE;
}
for (int i = MAXLEN - 1; i > 0; --i)
if (a[i]) {
a[0] = i;
break;
}
}
void dp(int i, int j) {
if (f[i][j][0])
return;
dp(i + 1, j);
dp(i, j - 1);
memset(tem1, 0, sizeof(tem1));
memset(tem2, 0, sizeof(tem2));
tem1[0] = f[i + 1][j][0];
for (int k = 1; k <= tem1[0]; ++k)
tem1[k] = f[i + 1][j][k];
plus(tem1, a[i]);
tem2[0] = f[i][j - 1][0];
for (int k = 1; k <= tem2[0]; ++k)
tem2[k] = f[i][j - 1][k];
plus(tem2, a[j]);
int x = cmp(tem1, tem2);
if (x >= 0) {
f[i][j][0] = tem1[0];
for (int k = 1; k <= tem1[0]; ++k)
f[i][j][k] = tem1[k];
from[i][j] = 1;
} else {
f[i][j][0] = tem2[0];
for (int k = 1; k <= tem2[0]; ++k)
f[i][j][k] = tem2[k];
from[i][j] = 2;
}
cheng(f[i][j]);
}
int main() {
scanf("%d%d", &n, &m);
for (int t = 1; t <= n; ++t) {
for (int i = 1; i <= m; ++i)
scanf("%d", &a[i]);
memset(f, 0, sizeof(f));
for (int i = 1; i <= m; ++i) {
f[i][i][0] = 1;
f[i][i][1] = a[i];
cheng(f[i][i]);
}
dp(1, m);
s_plus(ans, f[1][m]);
}
printf("%d", ans[ans[0]]);
for (int i = ans[0] - 1; i > 0; --i)
printf("%d%d%d%d", ans[i] / 1000, ans[i] / 100 % 10, ans[i] / 10 % 10, ans[i] % 10);
return 0;
}
评论:
using namespace std; const int N=100; int n,m; __int128 a[N][N],f[N][N]; template inline void read(T &x){
x=0;int w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
for(;ch>='0'&&ch<='9';ch=getchar())
x=(x<<3)+(x<<1)+(ch&15);
x*=w;
} inline void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
} int128 dp(int128 sum[]) {
memset(f,0,sizeof(f));
int i,j;
for(i=0;i<m;i++)//由于dp[i][j]是由大区间推出来的，所以先循环大区间
for(j=1;i+j<=m;j++)
f[j][i+j]=max(2*(f[j+1][i+j]+sum[j]),2*(f[j][i+j-1]+sum[i+j]));
return f[1][m];
} int main() {
read(n),read(m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
read(a[i][j]);
__int128 ans=0;
for(i=1;i<=n;i++)
ans+=dp(a[i]);//分行分别计算
write(ans);
return 0;
}
请先登录，才能进行评论