CodeForces A. Sereja and Swaps(暴力+贪心)

93 阅读 0 评论 62 点赞

我是靠谱客的博主紧张大象，这篇文章主要介绍CodeForces A. Sereja and Swaps(暴力+贪心)，现在分享给大家，希望可以做个参考。

题目链接：http://codeforces.com/problemset/problem/425/A

A. Sereja and Swaps

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

复制代码

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

output

复制代码

1
2
32

input

复制代码

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

output

复制代码

1
-1

题意：

求一个序列交换K次后的最大连续子序列和！

PS:

暴力枚举每一个区间！

代码如下：

复制代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
#define INF 0x3f3f3f3f
int MAX(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
int n, k;
int a[maxn];
int b[maxn], c[maxn];
int l1 = 0, l2 = 0;
int findd(int l, int r)
{
    for(int i = 1; i <= n; i++)
    {
        if(i >= l && i <= r)
        {
            b[++l1] = a[i];
        }
        else
        {
            c[++l2] = a[i];
        }
    }
    if(l1 < l2)
        return l1;
    return l2;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        int maxans = -INF;
        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++)
            {
                l1 = 0, l2 = 0;
                memset(b,0,sizeof(b));
                memset(c,0,sizeof(c));
                int num = findd(i, j);
                sort(b+1, b+l1+1);
                sort(c+1, c+l2+1);
                if(num > k)
                {
                    num = k;
                }
                for(int h = 1; h <= num; h++)
                {
                    if(c[l2-h+1] > b[h])
                    {
                        int tt = b[h];
                        b[h] = c[l2-h+1];
                        c[l2-h+1] = tt;
                    }
                }
                int tsum = 0;
                for(int l = 1; l <= l1; l++)
                {
                    tsum += b[l];
                }
                maxans = MAX(maxans,tsum);
            }
        }
        printf("%dn",maxans);
    }
    return 0;
}
/*
10 2
10 -1 2 2 2 2 2 2 -1 10
5 10
-1 -1 -1 -1 -1
1 1
-1
3 2
1 -1 2
3 1
1 -1 2
5 2
-1 -4 -5 -2 -3
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
#define INF 0x3f3f3f3f
int MAX(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
int n, k;
int a[maxn];
int b[maxn], c[maxn];
int l1 = 0, l2 = 0;
int findd(int l, int r)
{
    for(int i = 1; i <= n; i++)
    {
        if(i >= l && i <= r)
        {
            b[++l1] = a[i];
        }
        else
        {
            c[++l2] = a[i];
        }
    }
    if(l1 < l2)
        return l1;
    return l2;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        int maxans = -INF;
        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++)
            {
                l1 = 0, l2 = 0;
                memset(b,0,sizeof(b));
                memset(c,0,sizeof(c));
                int num = findd(i, j);
                sort(b+1, b+l1+1);
                sort(c+1, c+l2+1);
                if(num > k)
                {
                    num = k;
                }
                for(int h = 1; h <= num; h++)
                {
                    if(c[l2-h+1] > b[h])
                    {
                        int tt = b[h];
                        b[h] = c[l2-h+1];
                        c[l2-h+1] = tt;
                    }
                }
                int tsum = 0;
                for(int l = 1; l <= l1; l++)
                {
                    tsum += b[l];
                }
                maxans = MAX(maxans,tsum);
            }
        }
        printf("%dn",maxans);
    }
    return 0;
}
/*
10 2
10 -1 2 2 2 2 2 2 -1 10
5 10
-1 -1 -1 -1 -1
1 1
-1
3 2
1 -1 2
3 1
1 -1 2
5 2
-1 -4 -5 -2 -3
*/