30pts , 找不到错误

P2331 [SCOI2005] 最大子矩阵

你是m==2时有错 ```cpp #include<bits/stdc++.h> #define N 104 #define M 4 #define K 14 using namespace std; int n,m,k,ans=-INT_MAX; int a[N][M]; int dp[N][K][3]; void init(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } int main(){ init(); int op; for(int i=1;i<=n;i++) for(int j=1;j<=min(k,i);j++){ dp[i][j][0]=dp[i-1][j][0]; for(int k=j-1;k<i;k++)dp[i][j][0]=max(dp[i][j][0],dp[k][j-1][0]); dp[i][j][0]+=a[i][1]; ans=max(ans,dp[i][j][0]); } printf("%d",ans); return 0; } ```
by 黑影洞人 @ 2021-07-28 15:00:16


AC代码(要前缀和) ```cpp #include<cstdio> #include<algorithm> #define N 103 using namespace std; int m,n,k,a[N],b[N]; int dp2[N][N][N],dp[N][N]; int main(){ scanf("%d%d%d",&n,&m,&k); if(m==1){ for(int i=1;i<=n;i++){ int x; scanf("%d",&x); a[i]=a[i-1]+x; } for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ dp[i][j]=dp[i-1][j]; for(int t=0;t<i;t++){ dp[i][j]=max(dp[i][j],dp[t][j-1]+a[i]-a[t]); } } } printf("%d",dp[n][k]); } else{ for(int i=1;i<=n;i++){ int x,y; scanf("%d",&x); scanf("%d",&y); a[i]=a[i-1]+x; b[i]=b[i-1]+y; } for(int i=1;i<=k;i++){//k for(int j=1;j<=n;j++){ for(int t=1;t<=n;t++){ dp2[j][t][i]=max(dp2[j-1][t][i],dp2[j][t-1][i]); for(int l=0;l<j;l++)dp2[j][t][i]=max(dp2[j][t][i],dp2[l][t][i-1]+a[j]-a[l]+(j==t)*(dp2[l][l][i-1]-dp2[l][t][i-1]+b[t]-b[l])); for(int l=0;l<t;l++)dp2[j][t][i]=max(dp2[j][t][i],dp2[j][l][i-1]+b[t]-b[l]); //if(j==k)for(int l=0;l<j;l++)dp2[j][t][i]=max(dp2[j][t][i],f[l][l][i-1]+a[j]-a[l]); } } } printf("%d\n",dp2[n][n][k]); } return 0; } ```
by 黑影洞人 @ 2021-07-28 15:37:49


|