某种数列问题 (jx. cpp/c/pas)

众所周知, chenzeyu97 有无数的妹子 (阿掉!) , 而且他还有很多恶趣味的问题, 继上次纠结于一排妹子的排法以后, 今天他有非 (chi) 常 (bao) 认 (cheng) 真 (zhe) 去研究一个奇怪的问题. 有一堆他的妹子站成一排, 然后对于每个妹子有一个美丽度, 当然美丽度越大越好, chenzeyu97 妹子很多, 但是质量上不容乐观, 经常出现很多美丽度为负数的妹子 (喜闻乐见), chenzeyu97 希望从一排妹子里找出 3 队连续的妹子, 使她们的美丽度和最大. 注意, 一个妹子不能被编入多个队伍而且一定要拿出三队, 不然 czy 会闲着没事做~.

简单滴说就是:

给定一个数列, 从中找到 3 个无交集的连续子数列使其和最大.

输入文件

第一行一个数 n, 表示数列长度.

接下来有 n 行, 每行一个数, 第 i 行为第 i 个数.

输出文件

仅有一个数, 表示最大和.

样例输入

10
-1
2
3
-4
0
1
-6
-1
1
-2

样例输出

7

样例说明

第一队妹子取 2, 3.

第二队妹子取 0, 1.

第三队妹子取 1.

数据范围

请大家放心, 虽然 chenzeyu97 妹子无数, 但是这次他叫来的个数 n 是有限的.=v=

对于 30% 的数据, 妹子数不大于 200.

对于 60% 的数据, 妹子数不大于 2000.

对于 100% 的数据, 妹子数 1000000.

而且, 由于 chenzeyu97 没有 CCR 那样的影响力, 所以他的妹子选完的最大美丽度和不超过 maxlongint. (注: CCR 随便选就爆 long long, 因为他是把妹狂魔=V=).

Explanation

先枚举 dp [0] [i] 表示从最左边往右选到第 i 个位置妹子的美丽度最大值

然后再枚举 dp [1] [i] 表示从最右边往左选到第 i 个位置妹子的美丽度最大值

最后可以先 \(O(n)\) 预处理,\(O(1)\) 查询枚举中间的一队妹子的起点和终点来得到三队 妹子的美丽度最大值.

当然上面写的是 60 分暴力解法~

现在上正解: 枚举 dp [i] [j] [k] 表示在第 i 个位置, 已经选了 j 队妹子, 第 i-1 个人 有没有被选中 (即为 k), 然后转移方程自行看代码.

Source Code

先是部分分 (60) 解法:


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1000100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n;
lli arr[maxn],
    sum_d[maxn],
    dp_front[maxn],
    dp_rear[maxn];
#define sum(_l,_r) (sum_d[_r]-sum_d[(_l)-1])

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    // Calculate sum of individual items
    for (int i = 1; i <= n; i++)
        sum_d[i] = sum_d[i - 1] + arr[i];
    // Best consecutive team chosen from start...
    dp_front[0] = -infinit;
    for (int i = 1; i <= n; i++) {
        dp_front[i] = dp_front[i - 1];
        for (int j = 1; j <= i; j++)
            dp_front[i] = max(dp_front[i], sum(j, i));
    }
    // Best consecutive team chosen from end...
    dp_rear[n + 1] = -infinit;
    for (int i = n; i >= 1; i--) {
        dp_rear[i] = dp_rear[i + 1];
        for (int j = n; j >= i; j--)
            dp_rear[i] = max(dp_rear[i], sum(i, j));
    }
    // Choose at centre...
    lli res = -infinit;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            res = max(res, dp_front[i - 1] + sum(i, j) + dp_rear[j + 1]);
    // Output results.
    printf("%lld\n", res);
    return 0;
}

再是满分解法:


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1000100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

int n;
lli arr[maxn],
    dp[maxn][4][2];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    // dp[u][j][k]: At position #i, Chosen j teams, k indicates whether the
    // last person (a.k.a. person @ #i) was chosen
    dp[0][0][0] = 0; // Initial state
    dp[0][0][1] = -infinit; // Impossible...
    for (int j = 1; j <= 3; j++)
        dp[0][j][0] = dp[0][j][1] = -infinit; // Impossible...
    // Main dp procedure
    for (int i = 1; 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]);
            dp[i][j][1] = max(j > 0 ? dp[i - 1][j - 1][0] : -infinit, dp[i - 1][j][1]) + arr[i];
        }
    lli res = max(dp[n][3][0], dp[n][3][1]);
    printf("%lld\n", res);
    return 0;
}