拯救LongMM （递推公式求解）
拯救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.