「CF425A」Sereja and Swaps

2014年4月28日3,4620

As usual, Sereja has array a, its elements are integers: a[1], a[2], …, a[n]. Let’s introduce notation:

$\text{[math]}$ 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

1 2	10 2 10 -1 2 2 2 2 2 2 -1 10

output

32

input

5 10
-1 -1 -1 -1 -1

1 2	5 10 -1 -1 -1 -1 -1

output

-1

-1

题解

卧槽一开始看成相邻交换了。。。

枚举一个子串，将子串内尽量小的和子串外尽量大的尝试交换

然后没了。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 0x7fffffff
using namespace std;
int n,m,ans=-inf,a[201];
int a1[201],a2[201];
void cal(int l,int r)
{
    int t1=0,t2=0,s=0;
    for(int i=1;i<l;i++)a1[++t1]=a[i];
    for(int i=r+1;i<=n;i++)a1[++t1]=a[i];
    for(int i=l;i<=r;i++)a2[++t2]=a[i],s+=a[i];
    sort(a1+1,a1+t1+1);
    sort(a2+1,a2+t2+1);
    for(int i=1;i<=m&&i<=t1&&i<=t2&&a1[t1-i+1]>a2[i];i++)
    {
        s+=a1[t1-i+1];
        s-=a2[i];
    }
    ans=max(ans,s);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
       for(int j=i;j<=n;j++)
          cal(i,j);
    printf("%d",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 0x7fffffff

using namespace std;

int n,m,ans=-inf,a[201];

int a1[201],a2[201];

void cal(int l,int r)

{

int t1=0,t2=0,s=0;

for(int i=1;i<l;i++)a1[++t1]=a[i];

for(int i=r+1;i<=n;i++)a1[++t1]=a[i];

for(int i=l;i<=r;i++)a2[++t2]=a[i],s+=a[i];

sort(a1+1,a1+t1+1);

sort(a2+1,a2+t2+1);

for(int i=1;i<=m&&i<=t1&&i<=t2&&a1[t1-i+1]>a2[i];i++)

{

s+=a1[t1-i+1];

s-=a2[i];

}

ans=max(ans,s);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

for(int i=1;i<=n;i++)

for(int j=i;j<=n;j++)

cal(i,j);

printf("%d",ans);

return 0;

}

« 任务调度「BZOJ2288」「POJ Challenge」生日礼物 »

hzwer.com _ Home | http://hzwer.com

「CF425A」Sereja and Swaps

分类目录

热门文章

Myfriends

近期评论