AHSOFNU NOIP模拟题-5 T2(DP)

设$dp(i,j,0-1)$表示前$i$个数分了$j$组$i$选($1$)或$i$不选($0$)的最优值。

$dp(i, j, 0) = max(dp(i-1,j,0), dp(i-1,j,1))$
$dp(i, j, 1) = max(dp(i-1,j-1,0), dp(i-1,j-1,1), dp(i-1, j, 1))$
答案为$max(dp(n,3,1),dp(n,3,0))$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "jx"
using namespace std;
const int MAXN = 1000000 + 5, INF = 1000000000;
int n, ai[MAXN], dp[MAXN][4][2];
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*=10;x+=ch-'0';ch=getchar();}
return x*f;
}
void clean() {
for (int i=0;i<=n;i++) {
for (int j=0;j<=3;j++) {
dp[i][j][0] = dp[i][j][1] = -INF;
}
}
}
void solve() {
clean();
for (int i=1;i<=n;i++) ai[i] = read();
dp[1][0][0] = 0, dp[1][1][1] = ai[1];
for (int i=2;i<=n;i++) {
for (int j=0;j<=3;j++) {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]);
if (j-1>=0) dp[i][j][1] = max(dp[i-1][j-1][0]+ai[i], dp[i-1][j-1][1]+ai[i]);
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][1]+ai[i]);
}
}
printf("%d\n", max(dp[n][3][1], dp[n][3][0]));
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
n = read(), solve();
fclose(stdin); fclose(stdout);
return 0;
}

某种数列问题 (jx.cpp/c/pas) 1000MS 256MB

众所周知,chenzeyu97有无数的妹子(阿掉!>_<),而且他还有很多恶趣味的问题,继上次纠结于一排妹子的排法以后,今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排,然后对于每个妹子有一个美丽度,当然美丽度越大越好,chenzeyu97妹子很多,但是质量上不容乐观,经常出现很多美丽度为负数的妹子(喜闻乐见),chenzeyu97希望从一排妹子里找出3队连续的妹子,使她们的美丽度和最大。注意,一个妹子不能被编入多个队伍而且一定要拿出三队,不然czy会闲着没事做~。
简单滴说就是:
给定一个数列,从中找到3个无交集的连续子数列使其和最大。
【输入文件】
第一行一个数n,表示数列长度。
接下来有n行,每行一个数,第i行为第i个数。

【输出文件】
仅有一个数,表示最大和。

【样例输入】 jx.in
10
-1
2
3
-4
0
1
-6
-1
1
-2

【样例输出】 jx.out
7

【样例说明】
第一队妹子取2,3。
第二队妹子取0,1。
第三队妹子取1。

【数据范围】
请大家放心,虽然chenzeyu97妹子无数,但是这次他叫来的个数n是有限的。=v=
对于30%的数据,妹子数不大于200。
对于60%的数据,妹子数不大于2000。
对于100%的数据,妹子数1000000。
而且,由于chenzeyu97没有CCR那样的影响力,所以他的妹子选完的最大美丽度和不超过maxlongint。(注:CCR随便选就爆long long,因为他是把妹狂魔=V=)。

------ 本文结束 ------