题目传送门
Max Sum Plus Plus
题目大意
给你m个数，在其中选取n组 使得每组的数连续，且互相不能相交, 求出最大的各组数的和
思路
采取二维dp的方法
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]中，
i
i
i为组数，j为以
a
[
j
]
a[j]
a[j]结尾 状态转移方程为
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
−
1
]
[
j
]
+
a
[
j
]
,
d
p
[
i
−
1
]
[
k
]
+
a
[
j
]
)
(
0
<
k
<
j
)
dp[i][j]=max(dp[i-1][j]+a[j],dp[i-1][k]+a[j])(0<k<j)
dp[i][j]=max(dp[i−1][j]+a[j],dp[i−1][k]+a[j])(0<k<j) 因为复杂度为
O
(
n
2
)
O(n^2)
O(n2)，所以我们可以采取将二维dp变成一维dp，将其中的
d
p
[
i
−
1
]
[
k
]
dp[i-1][k]
dp[i−1][k]用一个单独的一维数组表示
AC Code
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std
;
#define INF 1<<30
const int N
=1e6 +9;
int n
, m
;
int dp
[N
], f
[N
], a
[N
];
int main(){
while(scanf("%d%d", &n
, &m
)!=EOF){
memset(dp
, 0, sizeof(dp
));
memset(f
, 0, sizeof(f
));
for(int i
=1; i
<=m
; i
++) scanf("%d", &a
[i
]);
int mx
=-INF
;
for(int i
=1; i
<=n
; i
++){
mx
=-INF
;
for(int j
=i
; j
<=m
; j
++){
dp
[j
]=max(dp
[j
-1], f
[j
-1])+a
[j
];
f
[j
-1]=mx
;
mx
=max(dp
[j
], mx
);
}
}
printf("%d\n", mx
);
}
return 0;
}
