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

思路：唉,dp是真的菜,想了半天屁思路都没。 先考虑一维情况,是求k个不相交的子段,区间和最大 状态为 d p ( i , j ) dp(i,j) dp(i,j)考虑前 i i i个数字选 j j j个区间. 如果考虑选用 a i a_i ai​,那么有 d p ( i , j ) = m a x ( d p ( k , j − 1 ) + s u m [ i ] − s u m [ k − 1 ] ) dp(i,j)=max(dp(k,j-1)+sum[i]-sum[k-1]) dp(i,j)=max(dp(k,j−1)+sum[i]−sum[k−1]) 如果不选 a i a_i ai​ d p ( i , j ) = d p ( i − 1 , j ) dp(i,j)=dp(i-1,j) dp(i,j)=dp(i−1,j) 二维的情况的话,就是新增加一个维度,同时考虑两列的选取情况 d p ( i , j , k ) dp(i,j,k) dp(i,j,k):第一个列选择了 i i i个,第二列选择了 j j j个,选出了 k k k个子矩阵的情况 情况1:选了第一列的第 i i i个,但是没有选第二列的 j j j d p ( i , j , k ) = m a x ( d p ( l , j − 1 , k − 1 ) + s u m [ i ] [ 1 ] − s u m [ l − 1 ] [ 1 ] ) dp(i,j,k)=max(dp(l,j-1,k-1)+sum[i][1]-sum[l-1][1]) dp(i,j,k)=max(dp(l,j−1,k−1)+sum[i][1]−sum[l−1][1]) 情况2：只选了第二列,但没有选第一列 d p ( i , j , k ) = m a x ( d p ( i , l , k − 1 ) + s u m [ j ] [ 2 ] − s u m [ l − 1 ] [ 2 ] ) dp(i,j,k)=max(dp(i,l,k-1)+sum[j][2]-sum[l-1][2]) dp(i,j,k)=max(dp(i,l,k−1)+sum[j][2]−sum[l−1][2]) 情况3:同时选中 i , j i,j i,j两个数字, 要求 i = = j 要求i==j 要求i==j d p ( i , j , k ) = m a x ( d p ( i − l , j − l , k − 1 ) + s u m [ i ] [ 1 ] − s u m [ i − l − 1 ] [ 1 ] + s u m [ j ] [ 2 ] − s u m [ j − l − 1 ] [ 2 ] 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] 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:两个都不选 d p ( i , j , k ) = m a x ( d p ( i − 1 , j − 1 , k ) ) dp(i,j,k)=max(dp(i-1,j-1,k)) dp(i,j,k)=max(dp(i−1,j−1,k)) 然后笔者本人叭叭写了一堆,发现情况4想假了,事实上是两个不选/ i i i不选, j j j也不选,但是已经生成了 k k k块子矩阵 也就是: 情况4: d p ( i , j , k ) = m a x ( d p ( i − 1 , j − 1 , k ) , d p ( i − 1 , j , k ) , d p ( i , j − 1 , k ) ) dp(i,j,k)=max(dp(i-1,j-1,k),dp(i-1,j,k),dp(i,j-1,k)) 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 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>a[i][1]>>a[i][2];
	}
	for(int i=1;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