Se consideră un șir de N numere naturale. O parte dintre poziţiile șirului sunt nevirusate și acest lucru este marcat prin faptul că valoarea de la acele poziţii este 0. Restul poziţiilor sunt virusate și valoarea nenulă de la o poziţie virusată reprezintă costul cu care ea poate fi devirusată. Devirusăm o parte dintre poziţii și dorim ca în final să avem exact K poziţii nevirusate, iar costul total al devirusării să fie minim. O poziţie poate fi devirusată la un moment dat, dacă și numai dacă are cel puţin o poziţie vecină nevirusată. După devirusarea unei poziţii costul asociat acesteia se adună la costul total, poziţia devine nevirusată si orice altă poziţie vecină virusată va putea fi ulterior devirusată.

Cerința

Cunoscând N, K și șirul de numere naturale să se determine costul minim cu care se pot obţine la final exact K poziţii nevirusate (incluzând şi poziţiile ce au fost iniţial nevirusate).

Date de intrare

Fișierul de intrare antivirus.in va conține pe prima linie numărul natural T – numărul de teste. Fiecare test este descris pe două linii. Pe prima linie se găsesc două numere naturale N și K cu semnificația din enunţ si pe a doua linie N numere naturale reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire antivirus.out trebuie să conțină T linii. Pe fiecare linie va fi afișat răspunsul pentru un test – un număr natural reprezentând costul minim al unei devirusări astfel încât în final șirul să conțină exact K poziții nevirusate – inclusiv cele care erau inițial nevirusate.

Restricții și precizări

1 ≤ T ≤ 4
1 ≤ K ≤ N ≤ 2000
pentru teste în valoare de 10 puncte se garantează că N ≤ 80
pentru alte teste în valoare de 20 puncte se garantează că N ≤ 200
pentru alte teste în valoare de 10 puncte în şirul iniţial există exact o poziție nevirusată
pentru alte teste în valoare de 10 puncte în şirul iniţial există exact 2 poziții nevirusate

Exemplu

antivirus.in

2
8 5
9 1 4 4 0 1 3 9
6 4
1 0 2 0 1 1

antivirus.out

10
2

Explicație

Sunt T = 2 teste. Pentru primul test se iau elementele de la indicii 2, 3, 4, 6 si se devirusează. Pentru al doilea test se iau elementele de la indicii 5 şi 6 şi se devirusează. O alta soluție validă ar fi fost indicii 1 şi 5.

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

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int kMaxN = 2000;
const int kMaxVal = 1e6;
const int kInf = (1LL << 31) - 1;

int v[kMaxN + 5];
int sum[kMaxN + 5];
int dp[kMaxN + 5][kMaxN + 5];

int main() {
  cin.sync_with_stdio(false);

  ifstream cin("antivirus.in");
  ofstream cout("antivirus.out");

  int t;
  cin >> t;

  for (; t; t--) {
    int n, m;
    cin >> n >> m;
    assert(n >= 1 && n <= kMaxN);
    assert(m >= 1 && m <= n);

    for (int i = 1; i <= n; i++) {
      cin >> v[i];
      assert(v[i] >= 0 && v[i] <= kMaxVal);
      if (v[i] == 0) {
        m--;
      }
      sum[i] = sum[i - 1] + v[i];
    }

    for (int i = 0; i < kMaxN; i++) {
      for (int j = 0; j < kMaxN; j++) {
        dp[i][j] = kInf;
      }
    }

    for (int i = 0; i <= n; i++) {
      dp[i][0] = 0;
    }

    int last = 0;
    for (int i = 1; i <= n; i++) {
      if (v[i] > 0) {
        if (last > 0) {
          for (int j = m; j > 0; j--) {
            dp[i][j] = dp[i - 1][j];
            if (j - (i - last) >= 0 && dp[last][j - (i - last)] != kInf) {
              dp[i][j] = min(dp[i][j], dp[last][j - (i - last)] + sum[i] - sum[last]);
            }
          }
        }
      } else {
        for (int j = 1; j <= m; j++) {
          dp[i][j] = dp[i - 1][j];
          for (int k = i - 1; k >= last; k--) {
            if (j - (i - k - 1) >= 0 && dp[k][j - (i - k - 1)] != kInf) {
              dp[i][j] = min(dp[i][j], dp[k][j - (i - k - 1)] + sum[i] - sum[k]);
            }
          }
        }
        last = i;
      }
    }

    ll ans = dp[n][m];
    cout << ans << '\n';
    assert(ans != kInf);
  }

  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 #2468 antivirus

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