Steven_MengのBlog

传送门

这道题把坑设在了数据范围里面,第一眼看上去没有思路,第二眼发现$m \le 2$,思路瞬间来了。

分情况讨论,分为$m=1$情况和$m=2$的情况。

声明,为了简略,我们设$sum(l,r)$为$\sum_{i=l}^{r}a[i]$,$sum1(l,r)$为$\sum_{i=l}^r=a[0][i]$,$sum2(l,r)$同理

$m=1$

这个$dp$方程比较容易,设$dp[i][j]$为搞到第$i$个数,总共$j$段的最大和。发现第$i$个数可选可不选,$dp[i-1][j]$为不选的情况。

方程为$dp[i][j]=\max(dp[i-1][j],dp[k-1][j]+sum(k,i))$

$m=2$

考虑这个$dp$方程,设$dp[i][j][p]$为第一行搞到第$i$个数,第二行搞到第$j$个数,总共$p$个矩阵,的最大和。

考虑每次可以从第一行转移一个$1$行的矩阵,第二行转移一个$1$行的矩阵,也可以从两行一起转移一个$2$行的矩阵,也可以什么都不转移。

考虑什么都不转移:$dp[i][j][p]=\max (dp[i-1][j][p],dp[i][j-1][p])$

考虑转移第一行:$dp[i][j][p]=\max(dp[l][j][p-1]+sum1(l+1,j))(l \in [0,i))$,第二列同理

转移第一行的情况:

转移第二行的情况:

注意,标成蓝色代表这里$dp$做完,并不代表全部选择,标成红色代表全部选择

考虑转移两行,只有在$i==j$的时候才有这种转移,因为$2$行的矩阵把状态一波推平,推出$dp[i][i][p]=\max (dp[l][l][p-1]+sum1(l+1,i)+sum2(l+1,i) ) (l \in [0,i))$

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
82
83
84
85
#include <bits/stdc++.h>
#define sum1(l,r) (s1[(r)]-s1[(l)-1])
#define sum2(l,r) (s2[(r)]-s2[(l)-1])
#define MAXN 105
#define MAXK 15
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
inline void chkmax(int &x,int y){
if (x<y) x=y;
}
int n,m,k;
namespace Solve1{
int a[MAXN];
int dp[MAXN][MAXK];
inline int Solve(){
for (register int i=1;i<=n;++i){
a[i]=read();
}
for (register int p=1;p<=k;++p){
for (register int i=1;i<=n;++i){
dp[i][p]=dp[i-1][p];
int sum=0;
for (register int j=i;j>=1;--j){
sum+=a[j];
chkmax(dp[i][p],dp[j-1][p-1]+sum);
}
}
}
printf("%d\n",dp[n][k]);
return 0;
}
}
namespace Solve2{
int a[2][MAXN];
int s1[MAXN],s2[MAXN];
int dp[MAXN][MAXN][MAXK];
//第一行搞到i第二行搞到j总共k个矩形
inline int Solve(){
for (register int i=1;i<=n;++i){
s1[i]=s1[i-1]+read();
s2[i]=s2[i-1]+read();
}
for (register int p=1;p<=k;++p){
for (register int i=1;i<=n;++i){
for (register int j=1;j<=n;++j){
dp[i][j][p]=max(dp[i-1][j][p],dp[i][j-1][p]);//可以什么也不搞
if (i==j){//可以2个2个地推进
for (register int l=0;l<i;++l){
chkmax(dp[i][j][p],dp[l][l][p-1]+sum1(l+1,i)+sum2(l+1,j));
}
}
for (register int l=0;l<i;++l){
chkmax(dp[i][j][p],dp[l][j][p-1]+sum1(l+1,i));
}
for (register int l=0;l<j;++l){
chkmax(dp[i][j][p],dp[i][l][p-1]+sum2(l+1,j));
}
}
}
}
printf("%d\n",dp[n][n][k]);
return 0;
}
}
int main(){
n=read(),m=read(),k=read();
if (m==1){
return Solve1::Solve();
}
else {
return Solve2::Solve();
}
}

 评论