A. Sereja and Swaps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
As usual, Sereja has array a, its elements are integers: a[1], a[2], ..., a[n]. Let's introduce notation:
A swap operation is the following sequence of actions:
- choose two indexes i, j (i ≠ j);
- perform assignments tmp = a[i], a[i] = a[j], a[j] = tmp.
What maximum value of function m(a) can Sereja get if he is allowed to perform at most k swap operations?
Input
The first line contains two integers n and k (1 ≤ n ≤ 200; 1 ≤ k ≤ 10). The next line contains n integers a[1], a[2], ..., a[n] ( - 1000 ≤ a[i] ≤ 1000).
Output
In a single line print the maximum value of m(a) that Sereja can get if he is allowed to perform at most k swap operations.
Sample test(s)
Input
10 2
10 -1 2 2 2 2 2 2 -1 10
Output
32
Input
5 10
-1 -1 -1 -1 -1
Output
-1 题意：给你一串数列，允许换K次位置，然后让你求一个最大的连续和
题解：暴力枚举区间就是！
int a[maxn];
vector<int>kiss;
vector<int>miss;
int main()
{
int n,m,ans,i,j,k;
while(cin>>n>>m)
{
for(i=;i<=n;i++)
scanf("%d",&a[i]);
ans=-inf;
for(i=;i<=n;i++)
{
int sum=;
for(j=i;j<=n;j++)
{
kiss.clear();
miss.clear();
sum=;
for(k=i;k<=j;k++)
{
kiss.push_back(a[k]);
sum+=a[k];
}
for(k=;k<=n;k++)
{
if(k<i||k>j)
miss.push_back(a[k]);
}
sort(kiss.begin(),kiss.end());
sort(miss.begin(),miss.end());
ans=max(ans,sum);
for(k=;k<=m&&k<=kiss.size()&&k<=miss.size();k++)
{
sum-=kiss[k-];
sum+=miss[miss.size()-k];
ans=max(ans,sum);
}
}
}
cout<<ans<<endl;
}
return ;
}