3 solutions
-
0
Guest MOD
-
1
#include<bits/stdc++.h> #define ll long long #define fo(i,x,y) for(register int i=x;i<=y;++i) #define go(i,x,y) for(register int i=x;i>=y;--i) using namespace std; inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; } const int N=1005; int a[N][N],n,m,S[N][N]; ll dp[N][N],pre[N],suf[N]; int main(){ n=read(),m=read(); fo(i,1,n) fo(j,1,m) a[i][j]=read(); fo(j,1,m) fo(i,1,n) S[j][i]=S[j][i-1]+a[i][j];//每一列的前缀和 pre[0]=suf[n+1]=-1e17; //由于转移的方式是从前一列直接到后一列 //因此第一列中除了第一行的元素其余的dp值均应赋为-inf,意为无法到达 fill(dp[1]+2,dp[1]+1+n,-1e17); dp[1][1]=a[1][1]; fo(i,2,m+1){//按列进行转移 //预处理pre和suf数组 fo(j,1,n) pre[j]=max(pre[j-1],dp[i-1][j]-S[i-1][j]); go(j,n,1) suf[j]=max(suf[j+1],dp[i-1][j]+S[i-1][j-1]); fo(j,1,n) dp[i][j]=max(pre[j]+S[i-1][j],suf[j]-S[i-1][j-1])+a[j][i]; } cout<<dp[m+1][n]; return 0; }
Information
- ID
- 77
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 44
- Accepted
- 10
- Uploaded By