Rezolvare completă PbInfo #1194 Fence

Un proprietar vinde un teren de formă dreptunghiulară împărțit în MxN parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă V lei. Vlad s-a interesat și a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteț, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu 2M+2N unități. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porțiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziționat să conțină și cele patru parcele de acces la exterior.

Cerința

Cunoscând M și N – dimensiunile terenului, V – prețul de cumpărare al fiecărei parcele, x_nord, x_sud, y_vest și y_est – pozițiile parcelelor cu acces la drumul exterior și A[i][j], 1≤i≤M și 1≤j≤N – valorile de revânzare pentru fiecare parcelă, să se determine:

a) Profitul P_arie_minimă pe care-l poate obține Vlad după cumpărarea și apoi revânzarea suprafeței de teren de arie minimă, împrejmuită conform condițiilor negociate.
b) Profitul maxim P_max pe care-l poate obține Vlad după cumpărarea și apoi revânzarea unei suprafețe de teren împrejmuită conform condițiilor negociate.

Date de intrare

Fișierul fence.in conține pe prima linie numărul t.
Pentru toate testele de intrare numărul t poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele M, N, V, x_nord, x_sud, y_vest și y_est separate prin câte un spațiu, iar pe următoarele M linii se află câte N numere naturale separate prin câte un spațiu, reprezentând valorile de revânzare ale celor MxN parcele de teren.

Date de ieșire

Dacă valoarea lui t este 1, atunci se va rezolva numai punctul a) din cerință.
În acest caz în fișierul de ieșire fence.out se va scrie pe prima linie numărul P_arie_minimă.
Dacă valoarea lui t este 2, atunci se va rezolva numai punctul b) din cerință.
În acest caz în fișierul de ieșire fence.out se va scrie pe prima linie numărul P_max.

Restricții și precizări

  • 3 ≤ M ≤ 1 000
  • 3 ≤ N ≤ 1 000
  • 1 000 ≤ V ≤ 10 000
  • 2 ≤ x_nord ≤ N-1, 2 ≤ x_sud ≤ N-1, 2 ≤ y_vest ≤ M-1, 2 ≤ y_est ≤ M-1
  • (x_nord-x_sud)∙(y_est-y_vest) ≥ 0
  • 1 ≤ A[i][j] ≤ 20 000
  • Prin profit se înțelege suma valorilor de revânzare corespunzătoare parcelelor din suprafața împrejmuită din care se scade produsul dintre prețul de cumpărare V și numărul parcelelor împrejmuite, care poate fi și negativ.
  • Pentru rezolvarea corectă a primei cerințe se va obține 20% din punctaj.
  • Pentru 33% din testele corespunzătoare cerinței b) va fi îndeplinită condiția M ≤ 15 și N ≤ 15.

Exemplul 1

fence.in

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

fence.out

3

Explicație

M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2.

P_arie_minimă = (8+7+6+4+5+9+6+6+8+2+5+7+8)-6∙13 = 81-78 = 3

Exemplul 1

fence.in

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

fence.out

8

Explicație

M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2

P_max = ( 8+4+9+8+7+7+6+4+5+9+6+6+8+2+5+7+7+8)-6∙18 = 116 - 108 = 8

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

// prof. Ionel Vasile Pit-Rada

#include <fstream>
using namespace std;

long long   a[1000][1000], b[1000][1000], best[1000][1000];
int         m, n, v;
int         col_top, col_bottom, row_left, row_right;


long long sum(long long (*a)[1000], int p, int q, int m, int n)
{
    long long s = 0L;

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            s += a[p + i][q + j];

    return s;
}


void reflect_x(long long (*a)[1000], int p, int q, int m, int n)
{
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n/2; j++)
            swap(a[p + i][q + j], a[p + i][q + n - j - 1]);
}


void reflect_y(long long (*a)[1000], int p, int q, int m, int n)
{
    for (int i = 0; i < m/2; i++)
        for (int j = 0; j < n; j++)
            swap(a[p + i][q + j], a[p + m - i - 1][q + j]);
}


long long bestGain(long long (*a)[1000], int p, int q, int m, int n)
{
    long long   maxLeft, gain;

    for (int j = 0; j <= n; j++)
        for (int i = m; i >= 0; i--)
            b[i][j] = ((i == m) || (j == 0)) ? 0 : b[i + 1][j] + a[p + i][q + j - 1];

    for (int j = 1; j <= n; j++)
    {
        maxLeft = best[0][j-1];
        for (int i = 0; i <= m; i++)
        {
            maxLeft    = max<long long>(maxLeft, best[i][j-1]);
            best[i][j] = maxLeft + b[i][j];
        }
    }

    gain = best[0][n];
    for (int i = 0; i <= m; i++)
        gain = max<long long>(gain, best[i][n]);

    return gain;
}


int main()
{
    ifstream    f("fence.in");
    ofstream    g("fence.out");
    long long   gain;
    int p;
    f >> p;
    f >> m >> n >> v;
    f >> col_top >> col_bottom >> row_left >> row_right;
    col_top--; col_bottom--; row_left--; row_right--;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
        {
            f >> a[i][j];
            a[i][j] -= v;
        }

    gain = sum(a, 0, 0, m, n)
         - sum(a, 0, 0, row_left, col_top)
         - sum(a, 0, col_top + 1, row_right, n - col_top - 1)
         - sum(a, row_left + 1, 0, m - row_left - 1, col_bottom)
         - sum(a, row_right + 1, col_bottom + 1, m - row_right - 1, n - col_bottom - 1);
    if(p == 1)
    {
        g << gain << endl;
    }
    else
    {
        reflect_x(a, 0, 0, row_left, col_top);
        reflect_x(a, row_left + 1, 0, m - row_left - 1, col_bottom);
        reflect_y(a, row_left + 1, 0, m - row_left - 1, col_bottom);
        reflect_y(a, row_right + 1, col_bottom + 1, m - row_right - 1, n - col_bottom - 1);

        gain += bestGain(a, 0, 0, row_left, col_top)
              + bestGain(a, 0, col_top + 1, row_right, n - col_top - 1)
              + bestGain(a, row_left + 1, 0, m - row_left - 1, col_bottom)
              + bestGain(a, row_right + 1, col_bottom + 1, m - row_right - 1, n - col_bottom - 1);
        g << gain;
    }
    g.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 #1194 Fence

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