1 /* 2 http://codeforces.com/contest/426/problem/C 3 最多交换k个数的顺序，求a[i]的最大连续和 4 爆解 5 思路：Lets backtrack interval that should contain maximal sum. 6 To improve it we can swap not more then K minimal elements 7 in fixed interval to not more K maximal elements not 8 contained in our interval. As n is quite little we can 9 do it in any way. Author solution works O(n3?*?log(n)). 10 */ 11 #include <iostream> 12 #include <vector> 13 #include <string.h> 14 #include <algorithm> 15 #include <queue> 16 #include <set> 17 18 using namespace std; 19 int sum[210][210],a[210];//sum[i][j]保存从i到j的和 20 int main(){ 21 int n,k,i,j,o,ans; 22 cin>>n>>k; 23 for(i=0;i<n;i++) cin>>a[i];//输入 24 memset(sum,0,sizeof(sum));//清0 25 ans=-5000000;//最值 26 for(i=0;i<n;i++){ 27 sum[i][i]=a[i]; 28 if(sum[i][i]>ans) ans=sum[i][i]; 29 for(j=i+1;j<n;j++){ 30 sum[i][j]=sum[i][j-1]+a[j]; 31 if(sum[i][j]>ans) ans=sum[i][j]; 32 } 33 } 34 priority_queue<int> temp; 35 multiset<int> add; 36 for(i=0;i<n;i++){ 37 for(j=i;j<n;j++){ 38 for(o=i;o<=j;o++){//查找从i到j为负的最小的k个 39 if(a[o]<0) temp.push(a[o]); 40 if(temp.size()>k) temp.pop(); 41 } 42 if((j-i+1)==temp.size()){//全为负 43 sum[i][j]=temp.top(); 44 while(!temp.empty()) temp.pop();//清空 45 } 46 else{ 47 while(!temp.empty()){//清空 48 sum[i][j]-=temp.top();//将负的移出 49 temp.pop(); 50 } 51 } 52 53 add.clear();//清空add 54 //对于非[i,j]部分取k个最大正数 55 for(o=i-1;o>=0;o--){ 56 if(a[o]>0) add.insert(a[o]); 57 if(add.size()>k) add.erase(add.begin()); 58 } 59 for(o=j+1;o<n;o++){ 60 if(a[o]>0) add.insert(a[o]); 61 if(add.size()>k) add.erase(add.begin()); 62 } 63 while(!add.empty()){ 64 sum[i][j]+=*add.begin(); 65 add.erase(add.begin()); 66 } 67 if(sum[i][j]>ans) ans=sum[i][j];//更新ans 68 } 69 } 70 cout<<ans<<" "; 71 return 0; 72 }