Copyright notice : This article is an original blog article , It can't be reproduced without the permission of the blogger .

Topic link

  • 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);
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

    Copyright notice : This article is an original blog article , It can't be reproduced without the permission of the blogger . Topic link The question : Give two lengths respectively ...

  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 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 ...

  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 ...