题目链接

https://codeforces.com/problemset/problem/426/C

解题思路

先用前缀和求出每段区间的价值和；
暴力枚举区间，枚举到的区间要与剩余部分的元素进行交换；
交换规则：枚举到的区间从小到大排序，未枚举到的部分从大到小排序，用枚举到的区间中小的换未枚举到部分中大的，最多交换k次，若接下来的交换已经无法使枚举到的区间的价值和增加，也要break。

具体实现看代码

AC代码

//未用优先队列 139ms
#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=210;
const int INF=0x3f3f3f3f;

bool cmp(int a,int b)
{
    return a>b;
}

int n,k,sum[N],a[N],b[N],c[N],ans=-INF;

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    } 

    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    {
        int t=sum[j]-sum[i-1],nb=0,nc=0;
        for(int kk=i;kk<=j;kk++)    b[++nb]=a[kk];//b存枚举区间的各个元素价值
        for(int kk=1;kk<i;kk++)      c[++nc]=a[kk];//c存未枚举部分各个元素价值
        for(int kk=j+1;kk<=n;kk++)    c[++nc]=a[kk];
        sort(b+1,b+nb+1);//b从小到大排序
        sort(c+1,c+nc+1,cmp);//c从大到小排序
        for(int p=1;p<=nb && p<=nc && p<=k && c[p]>b[p];p++)//交换超过k次、交换超过总元素个数、接下来要交换的c中的比b小，都要退出循环
        t+=c[p]-b[p];//增量
        ans=max(ans,t);
    }
    cout<<ans<<endl;
}


//优先队列 140ms
#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=210;
const int INF=0x3f3f3f3f;

int n,k,sum[N],a[N],ans=-INF;

priority_queue<int,vector<int>,greater<int> > b;
priority_queue<int> c;

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    {
        int sm=sum[j]-sum[i-1];
        for(int t=i;t<=j;t++)     b.push(a[t]);
        for(int t=1;t<i;t++)    c.push(a[t]);
        for(int t=j+1;t<=n;t++)    c.push(a[t]);

        for(int p=1;p<=k;p++)
        {
            if(b.empty() || c.empty()) break;
            int bb=b.top(),cc=c.top();
            b.pop(),c.pop();
            if(bb<cc) sm+=cc-bb;
            else break;
        }

        ans=max(ans,sm);
        while(!b.empty()) b.pop();
        while(!c.empty()) c.pop();
    }
    cout<<ans<<endl;
}

总结

看到数据规模很小，但还是不会……
还用到了前缀和小技巧，直接想不到