http://codeforces.com/problemset/problem/425/A

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.

 

题意：长度为n的序列，最多执行k次<交换任意两个数的位置>操作，问最大连续和。

思路：自己一直在想正负与连续和等等的复杂关系，千算万算没有想到：因为这题数据很小，直接枚举任意区间作为最后选择的连续和序列，把这个区间外的大的尽可能替换掉区间内小的，如此暴力。复杂度O(n^3log(n))

这题貌似确实只能暴力，没有什么好的性质优化算法。

#include<bits/stdc++.h>
using namespace std;
#define maxn 300

int n,k,a[maxn],ans=-(1<<30);

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int l=1;l<=n;l++)
	{
		for(int r=l;r<=n;r++)
		{
			vector<int> b,c;
			int sum=0;
			for(int i=l;i<=r;i++)b.push_back(a[i]),sum+=a[i];
			for(int i=1;i<l;i++)c.push_back(a[i]);
			for(int i=r+1;i<=n;i++)c.push_back(a[i]);
			sort(b.begin(),b.end());
			sort(c.begin(),c.end());
			for(int i=0;i<min(k,(int)min(c.size(),b.size()));i++)
			{
				if(c[c.size()-1-i]<=b[i])break;
				sum=sum-b[i]+c[c.size()-1-i];
			}	
			ans=max(ans,sum);
		}
	}
	cout<<ans<<endl;
	return 0;	
}