P2331 [SCOI2005]最大子矩阵（dp）

思路：唉,dp是真的菜,想了半天屁思路都没。
先考虑一维情况,是求k个不相交的子段,区间和最大
状态为$dp(i,j)$考虑前$i$个数字选$j$个区间.
如果考虑选用$a_i$,那么有
$dp(i,j)=max(dp(k,j-1)+sum[i]-sum[k-1])$
如果不选$a_i$
$dp(i,j)=dp(i-1,j)$
二维的情况的话,就是新增加一个维度,同时考虑两列的选取情况
$dp(i,j,k)$:第一个列选择了$i$个,第二列选择了$j$个,选出了$k$个子矩阵的情况
情况1:选了第一列的第$i$个,但是没有选第二列的$j$
$dp(i,j,k)=max(dp(l,j-1,k-1)+sum[i][1]-sum[l-1][1])$
情况2：只选了第二列,但没有选第一列
$dp(i,j,k)=max(dp(i,l,k-1)+sum[j][2]-sum[l-1][2])$
情况3:同时选中$i,j$两个数字,$要求i==j$
$dp(i,j,k)=max(dp(i-l,j-l,k-1)+sum[i][1]-sum[i-l-1][1]+sum[j][2]-sum[j-l-1][2]$
情况4:两个都不选
$dp(i,j,k)=max(dp(i-1,j-1,k))$
然后笔者本人叭叭写了一堆,发现情况4想假了,事实上是两个不选/$i$不选,$j$也不选,但是已经生成了$k$块子矩阵
也就是:
情况4:
$dp(i,j,k)=max(dp(i-1,j-1,k),dp(i-1,j,k),dp(i,j-1,k))$
然后这题还可以选空矩阵,很坑,小于等于k的答案也是合法的.

#include
using namespace std;
const int maxn = 100+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
int a[maxn][3];
ll dp[maxn][maxn][12];
int sum[maxn][3];
int n,m,K;
void solve2(){
	for(int i=1;i<=n;i++){
		cin>>a[i][1]>>a[i][2];
	}
	for(int i=1;i<=n;i++){
		sum[i][1] = sum[i-1][1] + a[i][1];
		sum[i][2] = sum[i-1][2] + a[i][2];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++) dp[i][j][0] = 0;
	}
	ll ans = 0;
	for(int k=1;k<=K;k++){
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				//情况4, i,j两个点都不选/其中有一个不选
				if(i>=1&&j>=1) dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k]);
				if(i>=1) dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k]);
				if(j>=1) dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k]);
				for(int l=1;l<=n;l++){
					//情况1,选择第一列中的[i-l,i]
					if(i>=l) dp[i][j][k] = max(dp[i][j][k],dp[i-l][j][k-1]+sum[i][1]-sum[i-l][1]);
					//情况2选择第二列中的[j-l,j]
					if(j>=l) dp[i][j][k] = max(dp[i][j][k],dp[i][j-l][k-1]+sum[j][2]-sum[j-l][2]);
					//情况2:同时选择i,j这两个格子,需要i==j这个条件
					if(i>=l&&j>=l&&i==j) dp[i][j][k] = max(dp[i][j][k],dp[i-l][j-l][k-1]+
					sum[i][1]-sum[i-l][1] + sum[j][2]-sum[j-l][2]
					);
				}
				ans = max(ans,dp[i][j][k]);
			}
		}
	}
	cout<<ans<<"\n";
}
ll dp1[maxn][maxn];
void solve1(){
	for(int i=1;i<=n;i++) cin>>a[i][1];
	for(int i=1;i<=n;i++) sum[i][1] = sum[i-1][1] + a[i][1];
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=K;j++) dp1[i][j] = -INF;
//	}
	ll ans = 0;
	for(int i=0;i<=n;i++) dp1[i][0] = 0;
	for(int j=1;j<=K;j++){
		for(int i=1;i<=n;i++){
			dp1[i][j] = max(dp1[i][j],dp1[i-1][j]);
			for(int l=0;l<=i;l++){
				dp1[i][j] = max(dp1[i][j],dp1[i-l][j-1]+sum[i][1]-sum[i-l][1]);
			}
			ans = max(ans,dp1[i][j]);
		}
	}
	cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>K;
//	for(int i=0;i<=n;i++){
//		for(int i1=0;i1<=n;i1++){
//			for(int j=0;j<=K;j++) dp[i][i1][j] = -INF;
//		}
//	}
	if(m==2) solve2();
	else solve1();
}

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
80
81