首页 > 代码库 > Codeforces Round #243 (Div. 2)——Sereja and Swaps

Codeforces Round #243 (Div. 2)——Sereja and Swaps

题目链接

  • 题意:
    给定一个整数序列长度为n,可以至多交换k次,求最大连续区间和(1?≤?n?≤?200; 1?≤?k?≤?10)
  • 分析:
    自己上来先考虑的方向是:先找出最大连续区间和,然后逐个交换,但是这样没法处理。对于最大区间内的交换直接找出最小值即可,但是如果最优位置不在当前区间内,情况就不好处理了
    根据上述特点,方向应该是,固定区间长度,然后进行交换。这样的复杂度是O(n^3),对于数据可以接受

const int MAXN = 210;

int ipt[MAXN], ta[MAXN], tb[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
    int n, m;
    while (~RII(n, m))
    {
        FE(i, 1, n) RI(ipt[i]);
        int ans = -INF;
        FE(i, 1, n) FE(j, i, n)
        {
            int t1 = 0, t2 = 0;
            FE(k, i, j) ta[t1++] = ipt[k];
            FE(k, 1, i - 1) tb[t2++] = ipt[k];
            FE(k, j + 1, n) tb[t2++] = ipt[k];
            sort(ta, ta + t1); sort(tb, tb + t2);
            reverse(tb, tb + t2);
            int e = min(min(m, t1), t2);
            REP(k, e) ta[k] = max(ta[k], tb[k]);
            int sum = 0;
            REP(k, t1) sum += ta[k];
            ans = max(ans, sum);
        }
        WI(ans);
    }
    return 0;
}




Codeforces Round #243 (Div. 2)——Sereja and Swaps