Se consideră un șir de numere naturale a[1], a[2], …, a[n]. Asupra șirului efectuăm n operații. O operație constă din eliminarea unuia din numerele de la capetele șirului. Deci la primul pas se elimină fie a[1], fie a[n]. Dacă la pasul i se elimină elementul a[k], atunci costul eliminării este i * a[k].

Cerința

Să se determine costul maxim posibil total al celor n operații.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi pe următoarele n linii se citește câte un număr din șir.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând costul maxim total posibil al eliminării celor n numere din șir.

Restricții și precizări

1 ≤ n ≤ 2000
1 ≤ a[i] ≤ 1000

Exemplu

Intrare

Ieșire

Explicație

La primul pas se elimină 1 (costul 1 * 1), la pasul doi se elimină 3 (cost 2 * 3), la pasul al treilea se elimină 2 (cost 3 * 2), iar la ultimul pas se elimină 4 (cost 4 * 4). Costul total maxim va fi 1+6+6+16=29.

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 mxt:

#include <bits/stdc++.h>
#define nmax 2002
using namespace std;

int a[nmax], n;
int dp[nmax][nmax];
/**
  Programare dinamica metoda mixta
  dp[i,j] = costul maxim al eliminarii secventei a[i..j]

  Date initiale
  dp(i,i) = n * a[i] , i=1,n
  Recurente:
  dp(i,j)=max((n-(j-i))*a[i] + dp(i+1,j), dp(i,j-1) + (n-(j-i))*a[j]
  Solutia este în dp(1,n)
*/

int main()
{
    int i, j, pas;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    for (i = 1; i <= n; i++)
        dp[i][i] = n * a[i];

    for (pas = 1; pas < n; pas++)
        for (i = 1; i <= n - pas; i++)
        {
            j = i + pas;
            dp[i][j] = max( (n - (j - i)) * a[i] + dp[i + 1][j],
                           dp[i][j - 1] + (n - (j - i)) * a[j]);
        }
    cout << dp[1][n];
    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 #2293 mxt

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2293 mxt 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 #2293 mxt