题意:就是选出K个ab的子矩阵(a<n,b<m),不能选选过的点,然后问你这个K个子矩阵MAX;
题解:首先这题一定要看范围,M=2,那么矩阵就是最大就是N2,我们是不是可以直接枚举暴力来做。
(我们每一列求一个前缀和,第一列sum1,第二列sum2)
- 首先.我们讨论M=1,是不是矩阵就是一列,然后我们就是dp求区间最大值,dp[i][j]代表前i行里面选择j个的值,dp[i][j]=max(dp[h-1][j-1]+sum1[i]-sum[h-1]);
2.m==2,我们这时候就要开始讨论了 ,首先开一个f[i][j][k],代表选第一列前i行第二列前j行k个子矩阵最大值,那么我们首先选择第一列处理,那就是f[i]j][h]=max(f[a-1][j][h-1]+sum1[i]-sum1[a-1]),
然后第二列处理,f[i][j][h]=max(f[i][a-1][h-1]+sum2[j]-sum2[a-1]),
最后一种情况就是当两列都选择时候,i==j时,那么就是
f[i][j][h]=max(f[i][j][h],f[a-1][a-1][h-1]+sum1[i]-sum1[a-1]+sum2[i]-sum2[a-1]);
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug1(x) cout<<"xxx"<<endl; #define ll long long #define ull unsigned long long #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #define mse(a,b) memset(a,b,sizeof a); #define fro for #define it int using namespace std; const int maxx=1e6+100; const int mod=1e9+7; int sum1[maxx],sum2[maxx]; int dp[500][500],f[500][500][15]; //ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; } //inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } int main() { int n,m,k; cin>>n>>m>>k; if(m==1) { for(int i=1;i<=n;i++) { int x; cin>>x; sum1[i]=sum1[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 h=1;h<=i;h++) dp[i][j]=max(dp[i][j],dp[h-1][j-1]+sum1[i]-sum1[h-1]);} } cout<<dp[n][k]<<endl; } else { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; cin>>x; if(j==1) sum1[i]=sum1[i-1]+x; else sum2[i]=sum2[i-1]+x; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int h=1;h<=k;h++) { f[i][j][h]=max(f[i-1][j][h],f[i][j-1][h]); for(int a=1;a<=i;a++)///处理第一列 f[i][j][h]=max(f[i][j][h],f[a-1][j][h-1]+sum1[i]-sum1[a-1]); for(int a=1;a<=j;a++)///处理第二列 f[i][j][h]=max(f[i][j][h],f[i][a-1][h-1]+sum2[j]-sum2[a-1]); if(i==j) for(int a=1;a<=i;a++) f[i][j][h]=max(f[i][j][h],f[a-1][a-1][h-1]+sum1[i]-sum1[a-1]+sum2[i]-sum2[a-1]); } cout<<f[n][n][k]<<endl; } return 0; }