1 条题解
-
2hyh5609 LV 10 @ 2020-08-04 20:58:50
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #define gc getchar() #define ll long long #define ull unsigned long long #define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout) #define I inline using namespace std; const int N=805,M=N+5;const ull G=31; template<class o>I void qr(o &x) { char c=gc;int f=1;x=0; while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;} while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;} x*=f; } template<class o>I void qw(o x) { if(x<0)x=-x,putchar('-'); if(x/10)qw(x/10); putchar(x%10+48); } I void cmx(ll &a,ll b){if(a<b)a=b;} ll col[N][N],row[N][N],f[N][N][2],L[N],R[N],s[N],u[N][2],d[N][2],ans;int val[N][N],n,m,arr[N][N]; void calc() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) col[i][j]=col[i-1][j]+val[i][j], row[i][j]=row[i][j-1]+val[i][j]; memset(f,0xcf,sizeof(f)); for(int i=1;i<=n;i++)f[i][1][1]=col[i][1],f[i][1][0]=val[1][1]; for(int i=1;i<=m;i++)f[1][i][1]=val[1][1],f[1][i][0]=row[1][i]; for(int i=2;i<=n;i++) for(int j=2;j<=m;j++) { ll w=col[i][j]+row[i][j]-val[i][j]; cmx(f[i][j][0],f[i-1][j][0]); cmx(f[i][j][0],f[i-1][j-1][1]+w); cmx(f[i][j][0],f[i][j-1][0]+val[1][j]); cmx(f[i][j][1],f[i][j-1][1]); cmx(f[i][j][1],f[i-1][j-1][0]+w); cmx(f[i][j][1],f[i-1][j][1]+val[i][1]); } memset(L,0xcf,sizeof(L));memset(R,0xcf,sizeof(R)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cmx(L[i],f[i][j][1]); for(int i=1;i<=m;i++)s[i]=row[1][m]-row[1][i]; R[1]=row[1][m]; for(int i=2;i<=n;i++) for(int j=1;j<m;j++) { s[j]=max(s[j]+val[i][m],col[i][j+1]+row[i][m]-row[i][j+1]); cmx(R[i],f[i][j][0]+s[j]); } } void solve() { memcpy(val,arr,sizeof(val));calc(); for(int i=1;i<=n;i++)u[i][0]=L[i],u[i][1]=R[i]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) val[i][j]=arr[n-i+1][m-j+1]; calc();for(int i=1;i<=n;i++)d[i][0]=R[n-i+1],d[i][1]=L[n-i+1]; memcpy(val,arr,sizeof(val)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) col[i][j]=col[i-1][j]+val[i][j], row[i][j]=row[i][j-1]+val[i][j]; ll l=0,r=row[1][m-1]; for(int i=2;i<=n;i++) { cmx(u[i][0],l+col[i][1]); cmx(u[i][1],r+col[i][m]); cmx(u[i][0],r+col[i][m]+row[i][m]-val[i][m]); cmx(u[i][1],l+col[i][1]+row[i][m]-val[i][1]); cmx(l,u[i][0]-col[i][1]); cmx(r,u[i][1]-col[i][m]); } l=row[n][m],r=val[n][m]; cmx(ans,d[1][0]); cmx(ans,u[n][1]); for(int i=n-1;i>1;--i) { l=max(l+val[i][1],d[i][0]); r=max(r+val[i][m],d[i][1]); cmx(ans,l+u[i-1][0]); cmx(ans,r+u[i-1][1]); } } int main() { qr(n),qr(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) qr(arr[i][j]); solve(); for(int i=1;i<=n;i++) for(int j=i+1;j<=m;j++) swap(arr[i][j],arr[j][i]); swap(n,m); solve(); qw(ans);puts(""); return 0; }
- 1
信息
- ID
- 1996
- 难度
- 2
- 分类
- (无)
- 标签
- 递交数
- 28
- 已通过
- 22
- 通过率
- 79%
- 被复制
- 2
- 上传者