# 剑与魔法-解题报告

## 1.题面

5
c 10
c 12
e 2
c 1
e 2


13


【数据说明】
30%的数据满足 N<=20
60%的数据满足 N<=1,000
100%的数据满足 N<=200,000

## 3. 各种各样的算法

### 60% N<=1,000

f[i][j]表示到第i行，参加了j场战役的最大金币数
f[i][j]=max(f[i-1][j],f[i-1][j-1]+val[i]) (ch[i]=='c')
f[i][j]=f[i-1,j] (j&lt;=val[i]-1)

DP的正确性可以用最优子结构和重叠子问题（无后效性）来验证。

### 100% N<=200,000

1.输入一个事件
2.如果是“CASE”事件，把对应的值压入小根堆
3.如果是“END”事件，弹出小根堆中的值直到小根堆中的元素数量符合限制条件（heap.size&lt;=val-1)
4.重复1


（本人第一次正儿八经地证明，如果有错误，欢迎大神指出！）

## 4. AC代码（Pascal）

var
n,i,num,ans,val:longint;
ch:char;
heap:array[0..800005] of longint;

procedure swap(var a,b:longint);
var t:longint;
begin
t:=a; a:=b; b:=t;
end;

procedure up(u:longint);
var fa:longint;
begin
while u>1 do
begin
fa:=u>>1;
if heap[fa]>heap[u] then
begin
swap(heap[fa],heap[u]);
u:=fa;
end
else break;
end;
end;

procedure down(u:longint);
var son:longint;
begin
while (u*2<=num) or (u*2+1<=num) do
begin
if (u*2+1>num) or (heap[u*2]<heap[u*2+1]) then son:=u*2
else son:=u*2+1;
if heap[u]>heap[son] then
begin
swap(heap[u],heap[son]);
u:=son;
end
else break;
end;
end;

procedure push(val:longint);
begin
inc(num);
heap[num]:=val;
up(num);
end;

function pop():longint;
begin
pop:=heap[1];
swap(heap[1],heap[num]);
dec(num);
down(1);
end;

begin
num:=0;
for i:=1 to n do
begin
if ch='c' then push(val)
else begin
if i<n then
while num>val-1 do pop;
end;
end;
if num<val then writeln('-1')
else
begin
ans:=0;
while num>0 do
ans:=ans+pop();
writeln(ans);
end;
end.


### 2 thoughts on “剑与魔法-解题报告”

1. Thanks for every one of your effort on this web page. Kate really likes conducting investigations and it’s really simple to grasp why. My partner and i know all regarding the compelling ways you give invaluable tips by means of this blog and cause participation from people on this concept and our princess is really starting to learn a lot of things. Take pleasure in the remaining portion of the new year. Your performing a wonderful job.