Se consideră un șir de numere naturale a[1], a[2], …, a[n] așezate circular. Acest lucru înseamnă că a[1] are ca vecini numerele a[n] și a[2], iar a[n] are ca vecini pe a[n-1] și a[1]. Se consideră de asemenea un număr natural K.

Cerința

Să se determine suma maximă care se poate obține din exact K secvențe nevide, disjuncte și ne-vecine.

Date de intrare

Fișierul de intrare kds.in conține pe prima linie numerele naturale n și K, iar pe linia a doua, separate prin câte un spațiu, numerele a[1], a[2], …, a[n].

Date de ieșire

Fișierul de ieșire kds.out va conține un singur număr natural reprezentând suma maximă care se poate obține din K secvențe nevide, disjuncte și ne-vecine.

Restricții și precizări

2 ≤ 2*K ≤ n ≤ 10000
1 ≤ a[i] ≤ 10000, i=1..n
Două secvențe sunt disjuncte dacă nu au niciun element comun.
Două secvențe sunt ne-vecine dacă sunt separate prin cel puțin un element care nu aparține nici uneia din cele două secvențe.

Exemplu

kds.in

7 2
3 7 2 1 2 4 5

kds.out

Explicație

Cele două secvențe sunt 1 și 4 5 3 7
Atenție, nu se pot alege secvențele 3 7 2 și 2 4 5 pentru că ele sunt vecine (5 este vecin cu 3).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema KDS:

/* Mihail Cosmin Pit-Rada
    O(n * k)
*/
#include<fstream>
using namespace std;

ifstream  fin("kds.in");
ofstream fout("kds.out");

int N,K,a[10002], infinit=1000000000;
int best[10002];

int solve(int start, int stop, int ka){
    int k, i, x, y, z, j, t, v;

    ///best[start-1]=infinit;
    t=infinit;
    for(i=start;i<=stop;i++){
        if(a[i]<t)t=a[i];
        best[i]=t;
    }

    for(k=2;k<=ka;k++){
        j=start+2*k-4; x=best[j]; y=best[j+1]; t=infinit;
        for(i=j+2;i<=stop;i++){
            z=best[i]; v=a[i]+x; if(v<t)t=v;
            best[i]=t; x=y; y=z;
        }
    }
    return best[stop];
}
int main(){
    int i, S, v1, v2;
    fin>>N>>K;
    S=0;
    for(i=1;i<=N;i++){
        fin>>a[i];
        S=S+a[i];
    }
    v1=a[1]+solve(3,N-1,K-1);//prima secventa il contine pe a[1]
    v2=solve(2,N,K);//a[1] nu face parte din nici o secventa
    fout<<S-min(v1,v2)<<"
";
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1716 KDS

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1716 KDS de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1716 KDS