[SCOI2005]最大子矩阵
DP就好
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define lowbit(x) (x&-x) #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 100 #define Maxs 26 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } int n,m,k,ans,a[Maxn+1][3],f[Maxn+1][15][5],dp[Maxn+1][Maxn+1],sum[Maxn+1]; int main(){ qread(n),qread(m),qread(k); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ qread(a[i][j]); } } if(m==1){ ans=0; for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i][1]; mes(dp,0); for(int i=0;i<=n;i++)dp[i][0]=0; for(int j=1;j<=k;j++){ for(int i=1;i<=n;i++){ dp[i][j]=std::max(dp[i][j],dp[i-1][j]); for(int t=0;t<i;t++)dp[i][j]=std::max(dp[i][j],dp[t][j-1]+sum[i]-sum[t]); ans=std::max(ans,dp[i][j]); } } printf("%d\n",ans); return 0; } mes(f,128); f[1][0][0]=0; f[1][1][1]=a[1][1];f[1][1][2]=a[1][2]; f[1][2][3]=f[1][1][4]=a[1][1]+a[1][2]; for(int i=2;i<=n;i++){ for(int j=1;j<=k;j++){ int mx=f[0][0][0],mx1=f[0][0][0],mx2=f[0][0][0]; for(int l=0;l<=4;l++){ mx=std::max(mx,f[i-1][j][l]); mx1=std::max(mx1,f[i-1][j-1][l]); if(j-2>=0)mx2=std::max(mx2,f[i-1][j-2][l]); f[i][0][0]=0; } f[i][j][0]=mx;int aa=a[i][1]+a[i][2]; f[i][j][1]=std::max(std::max(f[i][j][1],mx1+a[i][1]),std::max(f[i-1][j][1],f[i-1][j][3])+a[i][1]); f[i][j][2]=std::max(std::max(f[i][j][2],mx1+a[i][2]),std::max(f[i-1][j][2],f[i-1][j][3])+a[i][2]); f[i][j][3]=std::max(std::max(std::max(f[i][j][3],f[i-1][j][3]+aa),mx2+aa),std::max(f[i-1][j-1][1],f[i-1][j-1][2])+aa); f[i][j][4]=std::max(std::max(f[i][j][4],mx1+aa),f[i-1][j][4]+aa); } } ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ for(int l=0;l<=4;l++){ ans=std::max(ans,f[i][j][l]); } } } printf("%d\n",ans); } |