这一题，乍一眼看上去只想到了最暴力的暴力——大概(n^4)吧。
仔细看看数据范围，发现(1 leq m leq 2)，这就好办了，分两类讨论。
我先打了(m=1)的情况，拿了30分。
就相当于最大(k)段子段和。
直接用(dp[i][j][0/1])数组表示第(i)个选了(j)段的最大值，0代表不选，1为选。
那么状态转移方程也很简单：
- (dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+t[i];)
- (dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);)
而(m=2)的情况怎么弄呢？
实际上设计好状态，状态转移方程就出来了。
设(f[i][j][0,1,2,3,4])表示第(i)行选(j)个矩阵的最大值。
- (f[i][j][0])表示不选第(i)行。
- (f[i][j][1])表示选第(i)行的左边一段。
- (f[i][j][2])表示选第(i)行的右边一段。
- (f[i][j][3])表示选第(i)行左边和右边，分别代表两个段。
- (f[i][j][4])表示选第(i)行左右两边，只代表一段。
那么状态转移方程也很好出来了。
-
(f[i][j][0]=max{f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]};)
-
(f[i][j][1]=max{f[i-1][j-1][0],f[i-1][j][1],f[i-1][j-1][2],f[i-1][j][3], f[i-1][j-1][4]}+a[i][0];)
-
(f[i][j][2]=max{f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j][2],f[i-1][j][3], f[i-1][j-1][4]}+a[i][1];)
-
(f[i][j][4]=max{f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j][3]}+a[i][0]+a[i][1];)
-
(if~(j>=2)~f[i][j][3]=max{f[i][j][3],f[i-1][j-2][4]+a[i][0]+a[i][1]};)
-
(f[i][j][4]=max{f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3],f[i-1][j][4]}+a[i][0]+a[i][1];)
那么状态转移方程出来了就上代码吧！
那么多(max)连在一起真是美如画呀～
#include <bits/stdc++.h>
#define N 101
#define K 11
using namespace std;
int n,m,k;
const int mx=0x3f3f3f3f;
int dp[N][K][2],t[N];
void work1()
{
for (int i=1;i<=n;++i) cin>>t[i];
for (int i=1;i<=n;++i)
for (int j=1;j<=k;++j) {
dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0])+t[i];
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
}
cout<<max(dp[n][k][0],dp[n][k][1]);
}
int f[N][K][5],a[N][2];
void work2()
{
memset(f,-mx,sizeof(f));
for (int i=0;i<=n;i++)
for (int j=0;j<=k;j++) f[i][j][0]=0;
for (int i=1;i<=n;++i) cin>>a[i][0]>>a[i][1];
for (int i=1;i<=n;++i)
for (int j=1;j<=k;++j) {
f[i][j][0]=max(f[i-1][j][0],max(f[i-1][j][1],max(f[i-1][j][2],max(f[i-1][j][3],f[i-1][j][4]))));
f[i][j][1]=max(f[i-1][j-1][0],max(f[i-1][j][1],max(f[i-1][j-1][2],max(f[i-1][j][3],f[i-1][j-1][4]))))+a[i][0];
f[i][j][2]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],max(f[i-1][j][2],max(f[i-1][j][3],f[i-1][j-1][4]))))+a[i][1];
f[i][j][3]=max(f[i-1][j-1][1],max(f[i-1][j-1][2],f[i-1][j][3]))+a[i][0]+a[i][1];
if (j>1) f[i][j][3]=max(f[i][j][3],f[i-1][j-2][4]+a[i][0]+a[i][1]);
f[i][j][4]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],max(f[i-1][j-1][2],max(f[i-1][j-1][3],f[i-1][j][4]))))+a[i][0]+a[i][1];
}
cout<<max(f[n][k][0],max(f[n][k][1],max(f[n][k][2],max(f[n][k][3],f[n][k][4]))));
}
int main()
{
cin>>n>>m>>k;m!=2?work1():work2();
return 0;
}