2803_sum_dp

lzusa 发布于 2017-10-29 1 次阅读

题目描述

N个数排成一个环，请选出不超过K段的连续的数，段与段间不能重叠，且使得选出的数和最大。

 

思路

应为是一个环，所以选的段数等于不选的段数，对于头尾相连的情况就可以用求一次最大值和一次最小值得出解

dp设f[i][j][0/1]表示前i个数分了j段，当前这个点选或不选

#include 
#include 
#include 
using namespace std;
#define N 1001000
#define fill(x, y) memset(x, y, sizeof(x))
#define INF 0x7f7f7f7f
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
int f[N][12][2];
int a[N];
inline int read()
{
    int x = 0, p = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
    return x * p;
}
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        tot += a[i];
    }
    fill(f, -0x7f);
    f[1][1][1] = a[1];
    f[1][0][0] = 0;
    int ans = -INF;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
            f[i][j][0] = max(f[i - 1][j][1], f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0]) + a[i];
            ans = max(ans, f[i][j][1]);
            ans = max(ans, f[i][j][0]);
        }
    int t = ans;
    fill(f, 0x7f);
    ans = INF;
    f[1][1][1] = a[1];
    f[1][0][0] = 0;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= k; j++)
        {
             f[i][j][0] = min(f[i - 1][j][1], f[i - 1][j][0]);
            f[i][j][1] = min(f[i - 1][j][1], f[i - 1][j - 1][0]) + a[i];
            ans = min(ans, f[i][j][1]);
            ans = min(ans, f[i][j][0]);    
        }
    printf("%d\n", max(t, tot - ans));
    return 0;
}

 

]]>