/* * Úloha 29-3-1 Verbování * Autor: Marek Černý */ #include #include #include #include using namespace std; constexpr int NESPOCITANO = -1; int n; vector> ulozene_hodnoty; vector v, z; void nacti_vstup() { cin >> n; // inicializace dvou dynamických polí velikosti n v = z = vector(n); for (int &v: v) cin >> v; for (int &z: z) cin >> z; // inicializace pro cachování hodnot ~ '[n][2]' ulozene_hodnoty.resize(n, {NESPOCITANO, NESPOCITANO}); } // funkce počítající B_i(muzeme_verbovat), // oproti popisu vzorového řešení indexujeme i=0..n-1 int B(int i, bool muzeme_verbovat) { if (i < 0) return 0; // uložený výsledek int val = ulozene_hodnoty[i][muzeme_verbovat]; if (val == NESPOCITANO) { // zkusíme vzít zbraně if (i > 0) val = max(val, B(i-2, false) + v[i-1] + z[i]); // zkusíme naverbovat if (muzeme_verbovat) val = max(val, B(i-1 , false) + v[i]); // vždy mužeme zkusit nechat zbraně i obyvatele napokoji val = max(val, B(i-1, true)); } // uložíme hodnotu a vrátíme výsledek return ulozene_hodnoty[i][muzeme_verbovat] = val; } string B_plan(int, bool); // Jak je možné v C++ vracet 'string' hodnotou bez zhoršení časové složitosti? // Vracený 'string' totiž není kopírován // ale přesouván (používá se tzv. move semantika), // což je v C++11 konstantní operace. V některých případech může dokonce // překladač změnit funkci tak, jako by byl 'string' předávat referencí. // Viz. norma jazyka: http://en.cppreference.com/w/cpp/language/copy_elision#Example string B_plan(int i, bool muzeme_verbovat) { if (i < 0) return ""; // nyní už známe hodnotu nejlepší volby int val = ulozene_hodnoty[i][muzeme_verbovat]; // hodnota 'B(i-2, false)' je totéž co 'ulozene_hodnoty[i-2][false]' // pokud bylo nejvýhodnější brát zbraně if (i > 0 && val == (B(i-2, false) + v[i-1] + z[i])) { return B_plan(i-2, false) + "VZ"; // Operátor '+' nebo 'string::append' // jsou v C++ amortizovaně konstantní operace, // to proto, že jsou odvozeny od 'vector::push_back'. // pokud bylo nejvýhodnější verbovat } else if (muzeme_verbovat && val == (B(i-1 , false) + v[i])) { return B_plan(i-1, false) + 'V'; // pokud bylo nejvýhodnější nebrat nic } else { return B_plan(i-1, true) + '-'; } } int main() { nacti_vstup(); cout << B(n-1, true) << endl; cout << B_plan(n-1, true) << endl; }