拯救L o n g M M ( l a n . p a s / c / c p p )
【题目描述】
LongDD 将军为了平息延续数年战乱，决定释放战俘营中所有的俘虏。然而，
LongDD 将军不打算释放敌军的统帅LongMM——因为这个家伙异常聪明，是个难缠的
对手。所以LongDD 将军决定把LongMM 用链子固定到墙上。链子由n 个环组成，每
个环有可能在墙上，也可能不在墙上。
“LongDD 将军，你为什么把我绑在墙上，不让我获得自由”，LongMM 咆哮道。
“但是，LongMM，你并没有被绑在墙上。我很确定你可以自己把链子解开”，
LongDD 将军回答道，“但是请你在天黑之前解开，否则我会因为你制造噪音把你重
新抓起来。”
请帮助LongMM 吧！链子由n 个环组成，编号为1,2,…,n。我们可以把每个环从
墙上取下来或者从新放回墙上，但是需要遵循如下规则：
- 每一步只能取下或者装上一个环
- 编号为1 的环可以随意取下或装上
- 如果编号为1,…,k-1 的环都取下了，并且编号为k 的环在墙上，我们可
以随意取下或者装上第k+1 个环
- 当所有环都取下来之后，LongMM 可以逃脱了
给定每个环的初始状态，请你编写程序计算LongMM 最少需要多少步才能逃脱。
程序名: lan
【输入格式】
* 第 1 行: 有一个整数n，(1<=n<=1000)，表示环的个数
* 第 2 行: 有n 个整数，第i 个整数O_i=0，表示第i 个环在初始的时候为摘下的
状态；如果O_i=1，表示第i 个环初始的时候为装在墙上的状态。
【输入样例】
4
1 0 1 0
【输出格式】
* 第 1 行: 只有一个整数，表示最少需要多少步才能让LongMM 逃脱。
【输出样例】
6
【输出解释】
先递推
然后 找规律 发现从后往前 ans=2^jn-2^j(n-1)+2^j(n-2)+..... (j[i]表示从左往右第i个1）
Program lan;
type
arr=record
len:longint;
d:array[1..1000] of longint;
end;
const
F=1000000;
var
n,i:longint;
ans:arr;
p2:array[1..1000] of arr;
a:array[1..1001] of longint;
procedure multipy;
var
i,j,k:longint;
begin
for k:=2 to 1000 do
begin
p2[k].len:=p2[k-1].len;
for i:=1 to p2[k-1].len do
begin
inc(p2[k].d[i],p2[k-1].d[i]*2);
inc(p2[k].d[i+1],p2[k].d[i] div F);
p2[k].d[i]:=p2[k].d[i] mod F;
end;
if p2[k].d[p2[k].len+1]<>0 then inc(p2[k].len);
end;
for k:=1 to 1000 do dec(p2[k].d[1]);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
Procedure add(a,b:arr;var c:arr);
var
i,j:longint;
begin
fillchar(c,sizeof(c),0);
c.len:=max(a.len,b.len);
for i:=1 to c.len do
begin
inc(c.d[i],a.d[i]+b.d[i]);
inc(c.d[i+1],c.d[i] div F);
c.d[i]:=c.d[i] mod F;
end;
if c.d[c.len+1]>0 then inc(c.len);
end;
procedure sub(a,b:arr;var c:arr);
var
i,j:longint;
begin
fillchar(c,sizeof(c),0);
c.len:=max(a.len,b.len);
for i:=1 to c.len do
begin
inc(c.d[i],a.d[i]-b.d[i]);
if c.d[i]<0 then
begin
inc(c.d[i],F);
dec(c.d[i+1],1);
end;
end;
while (c.len>1) and (c.d[c.len]=0) do dec(c.len);
end;
Procedure work;
var
i,j:longint;
flag:boolean;
begin
i:=n;
flag:=true;
while true do
begin
while (a[i]=0) and (i>1) do dec(i);
if a[i]=0 then exit;
if flag then add(ans,p2[i],ans)
else sub(ans,p2[i],ans);
dec(i);
if i=0 then exit;
flag:=not(flag);
end;
end;
Procedure pri;
var
i:longint;
begin
write(ans.d[ans.len]);
for i:=ans.len-1 downto 1 do
begin
if ans.d[i]<100000 then write('0');
if ans.d[i]<10000 then write('0');
if ans.d[i]<1000 then write('0');
if ans.d[i]<100 then write('0');
if ans.d[i]<10 then write('0');
write(ans.d[i]);
end;
writeln;
end;
begin
assign(input,'lan.in');
assign(output,'lan.out');
reset(input);
rewrite(output);
read(n);
for i:=1 to n do read(a[i]);
fillchar(ans,sizeof(ans),0);
fillchar(p2,sizeof(p2),0);
p2[1].len:=1;
p2[1].d[1]:=2;
multipy;
work;
pri;
close(input);
close(output);
end.