首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。