luogu P2331 [SCOI2005]最大子矩阵 序列DP
我们观察到m非常小。
考虑只有一行的情况,dp[i][o]表示[1,i]这一段中取出o个矩形，的最大价值。我们预处理出w[i][j]表示[i,j]这一段的最大子矩阵 。那么转移非常显然。
dp[i][o] = max(dp[j - 1][o] + w[j][i])
我们接着考虑两行的情况，我们类比一下，用dp[i][j][o]表示第一行[1,i]，第二行[1,j]，一共选了o个子矩阵的最大价值。同时预处理出w[i][j][0]，表示[i,j]这一段高为2的最大子矩阵，w[i][j][1]，表示[i,j]这一段，上面一行的最大子矩阵，w[i][j][2]表示[i,j]这一段的下面一行的最大子矩阵。那么我们考虑对于dp[i][j][o]，我们无非是从一个状态第一行取了一个子矩阵，得到，第二行去了一个子矩阵得到，取了一个高为2的子矩阵得到。那么转移依旧很显然，dp[i][j][o] = max(dp[u - 1][j][o] + w[u][j][1]) dp[i][j][o] = max(dp[i][u - 1][o] + w[u][j][2]) dp[i][j][o] = max(dp[u - 1][u - 1][o] + w[u][min(i,j)][0])三个转移方程。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 int n,m,k; 9 int vec[110][3],w[110][110],w1[110][110][3],dp[110][15],dp1[110][110][15]; 10 int main() 11 { 12 scanf("%d%d%d",&n,&m,&k); 13 for (int i = 1;i <= n;i++) 14 for (int j = 1;j <= m;j++) 15 scanf("%d",&vec[i][j]); 16 for (int i = 1;i <= n;i++) 17 vec[i][0] = vec[i][1] + vec[i][2]; 18 if (m == 1) 19 { 20 for (int i = 1;i <= n;i++) 21 { 22 int tp = 0; 23 for (int j = i;j <= n;j++) 24 { 25 tp = max(tp + vec[j][1],0); 26 w[i][j] = max(w[i][j - 1],tp); 27 } 28 } 29 // 30 for (int o = 1;o <= k;o++) 31 for (int i = 1;i <= n;i++) 32 for (int j = o;j <= i;j++) 33 dp[i][o] = max(dp[j - 1][o - 1] + w[j][i],dp[i][o]); 34 printf("%d ",dp[n][k]); 35 }else 36 { 37 for (int o = 0;o <= 2;o++) 38 for (int i = 1;i <= n;i++) 39 { 40 int tp = 0; 41 for (int j = i;j <= n;j++) 42 { 43 tp = max(tp + vec[j][o],0); 44 w1[i][j][o] = max(w1[i][j - 1][o],tp); 45 } 46 } 47 for (int o = 1;o <= k;o++) 48 for (int i = 1;i <= n;i++) 49 for (int j = 1;j <= n;j++) 50 { 51 for (int u = 1;u <= i;u++) 52 dp1[i][j][o] = max(dp1[u - 1][j][o - 1] + w1[u][i][1],dp1[i][j][o]); 53 for (int u = 1;u <= j;u++) 54 dp1[i][j][o] = max(dp1[i][u - 1][o - 1] + w1[u][j][2],dp1[i][j][o]); 55 for (int u = 1;u <= min(i,j);u++) 56 dp1[i][j][o] = max(dp1[u - 1][u - 1][o - 1] + w1[u][min(i,j)][0],dp1[i][j][o]); 57 } 58 printf("%d ",dp1[n][n][k]); 59 } 60 return 0; 61 }