• The question ：
Given a sequence of integers, the length is n. Can exchange at most k Time , Find the maximum continuous interval and (1 ≤ n ≤ 200; 1 ≤ k ≤ 10)
• analysis ：
My first consideration is ： First, find the maximum continuous interval and . And then exchange them one by one , But it can't be dealt with like this .

For the exchange in the maximum interval, we can find the minimum value directly , But suppose the optimal location is not in the current range , It doesn't matter
According to the above characteristics , The direction should be . Fixed interval length , And then exchange .

What is the complexity O(n^3), The data is acceptable

const int MAXN = 210;
int ipt[MAXN], ta[MAXN], tb[MAXN];
int main()
{
// freopen("in.txt", "r", stdin);
int n, m;
while (~RII(n, m))
{
FE(i, 1, n) RI(ipt[i]);
int ans = -INF;
FE(i, 1, n) FE(j, i, n)
{
int t1 = 0, t2 = 0;
FE(k, i, j) ta[t1++] = ipt[k];
FE(k, 1, i - 1) tb[t2++] = ipt[k];
FE(k, j + 1, n) tb[t2++] = ipt[k];
sort(ta, ta + t1); sort(tb, tb + t2);
reverse(tb, tb + t2);
int e = min(min(m, t1), t2);
REP(k, e) ta[k] = max(ta[k], tb[k]);
int sum = 0;
REP(k, t1) sum += ta[k];
ans = max(ans, sum);
}
WI(ans);
}
return 0;
}

Codeforces Round #243 (Div. 2)——Sereja and Swaps More articles about

1. Codeforces Round #243 (Div. 2)——Sereja and Table

Before I look at this question , Can you look at this paper first < A kind of algorithm composition method >, To put it bluntly, it is classified discussion , But this idea is very important Topic link The question : First of all, the definition of connection block is given : For adjacency ( Up and down and left and right ) The same number as a link block ...

2. Codeforces Round #243 (Div. 1)——Sereja and Two Sequences

3. Codeforces Round #243 (Div. 1)——Sereja and Squares

Topic link The question : to n A little bit , Find the number of squares that can be formed . The four sides are parallel to the axis The analysis of the great God : Classic questions We think about every kind of x coordinate , Obviously there is only <= sqrt{N} individual x The coordinates appear > sqrt{N} Time , We ...

4. Codeforces Round #243 (Div. 1)A. Sereja and Swaps violence

A. Sereja and Swaps time limit per test 1 second memory limit per test 256 megabytes input standard ...

5. Codeforces Round #243 (Div. 2) A~C

Topic link A. Sereja and Mugs time limit per test:1 secondmemory limit per test:256 megabytesinput:standar ...

6. Codeforces Round #243 (Div. 2) C. Sereja and Swaps

because n The relatively small , Direct violence solution #include <iostream> #include <vector> #include <algorithm> #include ...

7. Codeforces Round #243 (Div. 2) C. Sereja and Swaps( Priority queue violence )

subject The question : Find the maximum of any continuous sequence , This continuous sequence can be compared with other Value exchange k Time , For maximum Ideas : Violence enumerates all sequential sequences . I didn't do it right because First of all, I didn't read the question carefully , I didn't see the exchange , then , Thought it was dp Or greed With a little bit of greed , various ...

8. Codeforces Round #243 (Div. 2) Problem B - Sereja and Mirroring Reading

http://codeforces.com/contest/426/problem/B The symmetrical title probably means . It should be pointed out that , When the number of lines is odd , The answer is the number of lines themselves #include<iostream& ...

9. Codeforces Round #243 (Div. 2) B. Sereja and Mirroring

#include <iostream> #include <vector> #include <algorithm> using namespace std; in ...

Random recommendation

1. Java The relationship between class name and file name in

1.Java The saved file name must be the same as the class name : 2. If there is only one class in the file , The file name must match the class name : 3. One Java There can only be one... In the file public class : 4. If there is more than one class in the file , The file name must be the same as public Class names are the same ...

2. C In language getchar and putchar Detailed explanation

First of all give <The_C_Programming_Language> The examples in this book : #include <stdio.h> int main(){    int c;     c ...

3. (function(){}).call(window) Strict pattern of anonymous functions this Point to undefined

Last time in the group , See someone send out  (function(){}).call(window) Such a piece of code , What's the point of asking , In anonymous functions this It doesn't always point to window The? , Why call, I was also confused . ...

4. ubuntu Next use quick2wire control RespberryPi2 Of I2C

First , Open the raspberry pie I2C drive : see I2C Whether the driver has been loaded :ls /dev -l | grep i2c, If it's tangible like  i2c-x The results show that the driver has been loaded , Otherwise, the driver is not loaded , You need to do the following : modify ...

5. openSuSE12.1 zypper LAMP

LAMP By Apache MySQL PHP Composed of , Is in Linux One of the most popular software combinations , At present, there are many websites running on the Internet LAMP Server . Linux -  It's a sentimental open source operating system :Apache -  ...

6. 【HDOJ】2645 find the nearest station

bare BFS. /* 2645 */ #include <iostream> #include <queue> #include <cstdio> #include & ...

7. obtain client really IP address

1. The necessity of introduction log4j-1.2.14.jar package org.ydd.test; import java.util.Enumeration; import javax.servlet.ht ...

8. solve VS On Fatal error RC1015: Unable to open include file &amp;#39;afxres.h&amp;#39; problem

In the experiment VS2010 When a problem bothers me , It's open c++ After the project is completed ,rc Of dialog entrance . You can't drag control , It makes me crazy ... And the one with the most say is online Directions problem . . This is obviously not the problem . So I ...

9. Python Development 【 Chapter 18 】Web Framework Django【 The basic chapter 】

One . brief introduction Python There are many different Web frame ,Django Is the most representative of the heavyweight players , Many successful websites and APP Are based on Django. Django Is an open source Web Application framework , from P ...

10. linux crontab perform mysqldump Global backup is empty

There's a problem today , During scheduled backup To see the backup file , It turns out that the size is 0, perform Backup sh File backup , Backup sql The file size is normal . Tried several ways . Final solution : Question why : Because the environment variables I set It's right there sh in send ...