http://codeforces.com/contest/426/problem/C
题意:找出连续序列的和的最大值,可以允许交换k次任意位置的两个数。
思路:枚举区间,依次把区间内的比较小的数换成区间外的比较大的数。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; int a[],b[],c[];
int n,kk;
bool cmp(int aa,int bb)
{
return aa>bb;
} int main()
{
cin>>n>>kk;
int ans=-;
for(int i=; i<=n; i++)
{
cin>>a[i];
ans=max(ans,a[i]);
}
for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
int t=;
memset(b,,sizeof(b));
memset(c,,sizeof(c));
for(int k=i; k<=j; k++)
{
b[t++]=a[k];
}
int t1=;
for(int x=; x<i; x++)
{
c[t1++]=a[x];
}
for(int x=j+; x<=n; x++)
{
c[t1++]=a[x];
}
sort(b,b+t);
sort(c,c+t1,cmp);
int sum=;
for(int x=; x<=min(kk,t); x++)
{
if(b[x-]<c[x-]&&x<=t1)
{
sum+=c[x-];
}
else
sum+=b[x-];
}
for(int x=min(kk,t); x<t; x++)
{
sum+=b[x];
}
ans=max(ans,sum);
}
}
printf("%d\n",ans);
return ;
}