传送门

题目理解与强调

给定了一个长度为 $n$ 的序列，允许有 $k$ 次交换，每次可以在序列中交换任意两个数，输出其交换后子串可能的最大值。

题解

这道题是一个思维题，对算法要求低，只要你学会了语言，拥有思维能力就可以做出这道题。

首先分析一下，这题目是要求一个子串的最大值，数据范围又是 $1 \le n \le 200$ ，所以我们可以分别枚举这个子串的两个端点。又因为数据范围中 $−1000 \le a[i] \le 1000$ ，数字的范围很小，所以开两个桶分别记录下整个序列中每个数出现的次数以及在枚举的子串中每个数出现的次数，因为在下一步枚举交换元素的时候，我们不去枚举那些原来就在字串中的元素，怎么判断，就靠这两个桶。同时，在交换元素的时候，要注意到以下几点：

• 我们要交换的是子串内最小的元素和子串外最大的元素。
• 如果交换了的元素数量与 $k$ 相等时就停止交换。
• 如果交换了的元素数量与子串内元素数量相等时，就停止交换。
• 如果交换了的元素与子串外元素相等时，就停止交换。
• 如果要交换的子串外的元素小于要交换的字串内的元素，就停止交换。因为这种交换是不优的。

对于桶的处理，我们也要注意：

• 因为 $a[i]$ 的值可能是负数，所以在存桶的时候要离散化，把对应的元素 $+1000$ 后放进桶中，在处理答案的时候记得减去离散化所加的值。
• 每次枚举完一个字串记得把桶清空。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 2001
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int a[M],b[M],c[M],bucket[M],_bucket[M],ans=-inf,n,k;
int main()
{
    read(n),read(k);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        a[i]+=N;
        b[i]=a[i];
        _bucket[a[i]]++;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            int cnt=0,sum=0;
            for(int g=i;g<=j;g++)
            {
                c[++cnt]=b[g];
                bucket[b[g]]++;
                sum+=b[g];
            }
            sort(c+1,c+1+j-i+1);
            int now=0,gg=0;
            for(int g=n;g>=1;g--)
            {
                if(gg==k||gg==j-i+1||gg+j-i+1==n)
                    break;
                if(bucket[a[g]]!=_bucket[a[g]]&&a[g]>=c[now+1])
                {
                    gg++;
                    sum=sum+a[g]-c[++now];
                    bucket[a[g]]++;
                }
            }
            ans=max(ans,sum-(j-i+1)*N);
            for(int g=1;g<=n;g++)
            {
                bucket[b[g]]=0;
            }
        }
    }
    print(ans);
    return 0;
}