This is a classic dynamic programming problem and, like most DP problems, is simple if and only if you "get" the induction piece. Additionally, getting full points required figuring out (or knowing) a nice trick for when you need to calculate the sums of lots of different ranges.
== include(page="template/noprofile") ==
Reading the problem, it seems to be very clearly a DP problem. In particular, the fact that the line of coins is always a continuous subrange of the original line is a big clue, and that we should compute Bessie's optimal strategy on the range [i, j] (inclusive on both sides) in terms of smaller ranges. Suppose that s(i, j) is the sum of c[i], c[i+1], ..., c[j]. Let b(i, j) be the most that Bessie can win if she plays *first* on the subrange [i, j]. Then we see that
b(i, j) = max(c[i] + s(i+1, j) - b(i+1, j), c[j] + s(i, j-1) - b(i, j-1))
since s(i, j) - b(i, j) is, by definition, the most Bonnie can win if Bonnie plays *second* on the interval [i, j]. Actually, this equation is equivalent to
b(i, j) = max(s(i, j) - b(i+1, j), s(i, j) - b(i, j-1))
= s(i, j) - min(b(i+1, j), b(i, j-1))
which makes sense, since this is equivalent to *minimizing* the *maximum* that Bonnie could win.
h2. Despre mine
This gives us an O(n^3) solution, if we compute s(i, j) out each time. In retrospect, if you computed all n^2 values of s(i, j) first, and then ran this DP solution, that would be O(n^2). That wasn't the solution I had in mind, though, and there's a trick to be learned here! The trick is that you compute *partial* sums: you define an array S[i] = c[0] + c[1] + ... + c[i-1], with length n+1. Then c[i] + c[i+1] + ... + c[j-1] = S[j] - S[i], which takes constant time to compute. This is a cute trick that is extremely useful to remember.
_(completeaza aici: studii, an de absolvire, institutie de invatamant, locatie, profesori pregatitori, site personal ...)_
h1 http://infoarena.ro/problema/ciclu
COBAI
NOV 09 - 80
NOV 10 - 82
NOV 11 - 84
NOV 12 - 85
NOV 15 - 86
DEC 05 - 89
DEC 06 - 90
DEC 09 - 92
DEC 10 - 93
DEC 11 - 94
DEC 12 - 98
DEC 13 -100
DEC 14 -101
DEC 15 -102
Task 200 probleme pana la 5 IAN
22 zile 100 probleme to go.
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4184
Retine smenul de la sir23
Ai grija la '\n' problema nc
h2. Distinctii primite
greseli
difprim 100 mii in loc de 10 milioane
qtri depinde la float long long timp int
grarb afisare pe dos
palalila2 zig zag nu merge invers? oare?
De facut problemele Balaur, Anticip si Microvirus de pe campion.
si http://acm.timus.ru/problem.aspx?space=1&num=1081
.
.
.
Probleme cu deque:knumere
.
.
.
..
.
..
.
.
.
.
h1. Selectati destinatia.
h3. "%{color:orange}Programare dinamica%":cauta-probleme?tag_id%5B%5D=58
* "Probleme ad-hoc":cauta-probleme?tag_id%5B%5D=68
* "Problema rucsacului":cauta-probleme?tag_id%5B%5D=95
Knapsack cu vector fara matrice de aparitii
for i = 1 la n
for j = S la 0
dp[j]=d[j-g[i]]+c[i]
* "Dinamica pe stari exponentiale":cauta-probleme?tag_id%5B%5D=59
* "Dinamica pe arbore":cauta-probleme?tag_id%5B%5D=71
* "Memoizare":cauta-probleme?tag_id%5B%5D=77
* "Exponentiere rapida de matrice":cauta-probleme?tag_id%5B%5D=283
h3. "%{color:orange}Grafuri%":cauta-probleme?tag_id%5B%5D=46
* "Parcurgere in latime **BFS**":cauta-probleme?tag_id%5B%5D=47 "^[problema clasica]^":problema/bfs
* "Parcurgere in adancime **DFS**":cauta-probleme?tag_id%5B%5D=69 "^[problema clasica]^":problema/dfs
* "Algoritmul lui Dijkstra":cauta-probleme?tag_id%5B%5D=72 "^[problema clasica]^":problema/dijkstra
* "Algoritmul Bellman-Ford":cauta-probleme?tag_id%5B%5D=92 "^[problema clasica]^":problema/bellmanford
* "Flux maxim":cauta-probleme?tag_id%5B%5D=268 "^[problema clasica]^":problema/maxflow
* "Flux maxim de cost minim":cauta-probleme?tag_id%5B%5D=93 "^[problema clasica]^":problema/fmcm
* "Lowest Common Ancestor":cauta-probleme?tag_id%5B%5D=82 "^[problema clasica]^":problema/lca
* "Lant hamiltonian":cauta-probleme?tag_id%5B%5D=57
* "Lant eulerian":cauta-probleme?tag_id%5B%5D=112
* "2-SAT":cauta-probleme?tag_id%5B%5D=87 "^[problema clasica]^":problema/2sat
* "Componente tare conexe":cauta-probleme?tag_id%5B%5D=88 "^[problema clasica]^":problema/ctc
* "Componente biconexe":cauta-probleme?tag_id%5B%5D=433
h3. "%{color:blue}Structuri de date%":cauta-probleme?tag_id%5B%5D=38
* "Hash":cauta-probleme?tag_id%5B%5D=432
* "Heapuri":cauta-probleme?tag_id%5B%5D=285
* "Arbori de intervale":cauta-probleme?tag_id%5B%5D=84 "^[problema clasica]^":problema/arbint
* "Arbori indexati binar":cauta-probleme?tag_id%5B%5D=106 "^[problema clasica]^":problema/aib
* "Arbori indexati binar 2D":cauta-probleme?tag_id%5B%5D=85
* "Arbori echilibrati":cauta-probleme?tag_id%5B%5D=350
* "Trie":cauta-probleme?tag_id%5B%5D=76 "^[problema clasica]^":problema/trie
* "Deque":cauta-probleme?tag_id%5B%5D=94 "^[problema clasica]^":problema/deque
* "Multimi disjuncte/ disjoint datasets":cauta-probleme?tag_id%5B%5D=296
* "Range Minimum Query":cauta-probleme?tag_id%5B%5D=83 "^[problema clasica]^":problema/rmq
* "Ortogonal Range Search":cauta-probleme?tag_id%5B%5D=297
h3. "%{color:red}Cautare%":cauta-probleme?tag_id%5B%5D=48
* "Cautare binara":cauta-probleme?tag_id%5B%5D=49 "^[problema clasica]^":problema/cautbin
h3. "%{color:green}Sortare%":cauta-probleme?tag_id%5B%5D=63
* "Sortare":cauta-probleme?tag_id%5B%5D=64
h3. "%{color:purple}Siruri de caractere%":cauta-probleme?tag_id%5B%5D=55
* "Parsare":cauta-probleme?tag_id%5B%5D=67
* "KMP":cauta-probleme?tag_id%5B%5D=56
* "Suffix array/ siruri de sufixe":cauta-probleme?tag_id%5B%5D=431
h3. "%{color:red}Backtracking%":cauta-probleme?tag_id%5B%5D=96
* "Submultimi":cauta-probleme?tag_id%5B%5D=98 "^[problema clasica]^":problema/submultimi
h3. "%{color:purple}Greedy%":cauta-probleme?tag_id%5B%5D=61
* "Ad-hoc":cauta-probleme?tag_id%5B%5D=70
h3. "%{color:black}Divide et Impera%":cauta-probleme?tag_id%5B%5D=89
* "Ad-hoc":cauta-probleme?tag_id%5B%5D=90
h3. "%{color:black}Matematica%":cauta-probleme?tag_id%5B%5D=40
* "Ciurul lui Eratostene":cauta-probleme?tag_id%5B%5D=101 "^[problema clasica]^":problema/ciur
* "Algoritmul lui Euclid":cauta-probleme?tag_id%5B%5D=43 "^[problema clasica]^":problema/euclid2
* "Exponentiere rapida":cauta-probleme?tag_id%5B%5D=262 "^[problema clasica]^":problema/lgput
* "Formula":cauta-probleme?tag_id%5B%5D=105
* "Combinatorica":cauta-probleme?tag_id%5B%5D=281
h3. "%{color:black}Geometrie%":cauta-probleme?tag_id%5B%5D=41
* "Ad-hoc":cauta-probleme?tag_id%5B%5D=62
* "Baleiere":cauta-probleme?tag_id%5B%5D=80
* "Aria unui poligon":cauta-probleme?tag_id%5B%5D=110
* "Intersectie de poligoane":cauta-probleme?tag_id%5B%5D=295
* "Teorema lui Pick":cauta-probleme?tag_id%5B%5D=111
* "Infasuratoare convexa":cauta-probleme?tag_id%5B%5D=265 "^[problema clasica]^":problema/infasuratoare
* "Rotating calipers":cauta-probleme?tag_id%5B%5D=266
* "No fit polygon":cauta-probleme?tag_id%5B%5D=259
h3. "%{color:red}Teoria jocurilor%":cauta-probleme?tag_id%5B%5D=60
* "Ad-hoc":cauta-probleme?tag_id%5B%5D=78
h3. "%{color:green}Diverse%":cauta-probleme?tag_id%5B%5D=45
* "Operatii pe biti":cauta-probleme?tag_id%5B%5D=73
* "Operatii pe numere mari":cauta-probleme?tag_id%5B%5D=104
* "Evaluare de expresii":cauta-probleme?tag_id%5B%5D=91 "^[problema clasica]^":problema/evaluare
* "Normalizare":cauta-probleme?tag_id%5B%5D=298
.
.
.
.
.
.
.
...
.
.
.
.
.
.
.
.
.
-afisati numarul total de inregistrari din tabela voturi!
Select count(judet), count(nr_voturi) from voturi
-determinati pentru cate judete avem rezultatele votarii folosind tabela voturi
-sa se determine cel mai mare numar de voturi exprimate pentru un candidat intr-un judet
-sa se determine numarul de voturi primite de catre un candidat raportat la numarul de alegatori
-cel mai mare numar de voturi obtinut de catre un candidat intr-un judet
-procentul obtinut de catre fiecare candidat in fiecare judet
-numarul total de voturi in judetul sibiu
-procentul mediu obtinut de un candidat in toate judetele(cod 12)
-calculati numarul total de vturi obtinut de fiecvare candidat in toate cele 3 judete
-select candidat,numar_votuir
-aflati procentul mediu obtinut de fiecare candidat in toate cele 3 judete
-afisati toti candidatii care au obtinut un procent in alegeri mai mare de 5% din numarul total de persoane cu drept de vot
-afisati angajatii care au salariul mai mare decat salariul lui Ionescu
-afisati toate persoanele care lucreaza la aceiasi firma la care lucreazxa si ionescu
-afisati toate persoanele care nu locuiesc in aceiasi localitate cu ionescu
-afisati toate persoanele care lucreaza in aceiasi localitate in care si locuiesc
'
set default toF:\12c
set default to F:\12c
set default to F:/12c
set default to F:\12c
OPEN DATABASE f:\12c\data1.dbc EXCLUSIVE
MODIFY DATABASE
select count(judet), count(numar_voturi) from voturi
select count(distinct judet) from voturi
select max(numar_voturi) from voturi
select max(100*numar_voturi/numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where judet=judete.cod_judet
select sum(numar_voturi) from voturi where judet="sb"
select sum(numar_voturi) from voturi where judet="SB"
select avg(100*numar_voturi/numar_alegatori) from voturi,judete where (candidat=12 and voturi.judet=judete.cod_judet)
select candidat,sum(numar_voturi) as total_voturi from voturi group by candidat
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where judet=judete.cod_judet
select 100*numar_voturi/numar_alegatori, judete.judet,candidat from voturi,judete where voturi.judet=judete.cod_judet
select candidat,numar_voturi from voturi group by candidat,numar_voturi
select candidat,avg(100*numar_voturi/numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat
select candidat,100*sum(numar_voturi)/sum(numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat
select candidat,100*sum(numar_voturi)/sum(numar_alegatori) from voturi,judete where voturi.judet=judete.cod_judet group by candidat having 100 * sum(numar_voturi)/sum(numar_alegatori)>5
select nume from angajati where salariul > (select salariul from angajati where nume="IONESCU")
select a.nume from persoane a,persoane b where a.idfirma=b.idfirma and b.nume="IONESCU"
select nume from persoane where idfirma=(select idfirma from persoane where nume="IONESCU")
select nume from persoane where localitate<>(select localitate from persoane where nume="IONESCU")
select nume from persoane where localitate=(select localitate from firme where idfirma=id)
* _(completeaza aici: locuri obtinute la concursuri de informatica)_
h2. Prieteni pe infoarena
* _(completeaza aici: link-uri catre profilele altor utilizatori infoarena pe care ii cunosti)_
