P1805 关灯

f[n]

=0,n=0

else =f[n-1],s[n]=0

else =2^n-1,s[i]=0,1<=i<=n-1

else =f[k-1]+2^n-2^k,k为1到n-1中最后一个一位数

#include<iostream>
#include<cstring>
#include<cstdio>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int maxn=1010;
int maxx(int a,int b){return a<b?b:a;}

struct Bn{
    int s[maxn],lon;
    Bn(){
        memset(s,0,sizeof(s));
        lon=0;
    }
    void clear(){
        while(lon&&s[lon]==0)lon--;
    }
    Bn operator + (const Bn &b)const{
        Bn Ans;
        Ans.lon=maxx(lon,b.lon);
        rep(i,0,Ans.lon){
            Ans.s[i]+=s[i]+b.s[i];
            if(Ans.s[i]>=10)
            Ans.s[i+1]++,
            Ans.s[i]-=10;
        }
        Ans.lon++;
        Ans.clear();
        return Ans;
    }
    Bn operator - ( Bn &b)const{
        Bn Ans=*this;
        rep(i,0,Ans.lon){
            Ans.s[i]-=b.s[i];
            if(Ans.s[i]<0)
            Ans.s[i+1]--,
            Ans.s[i]+=10;
        }
        Ans.clear();
        return Ans;
    }
    void coutt(){
        clear();
        dwn(i,lon,0)printf("%d",s[i]);
    }
}f[maxn],mi2[maxn];
int n,a[maxn];
int main(){
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",&a[i]);
    mi2[0].s[0]=1;
    rep(i,1,n){
        mi2[i]=mi2[i-1]+mi2[i-1];
        if(a[i]==0){
            f[i]=f[i-1];
            continue;
        }
        int re=-1;
        dwn(j,i-1,1)
        if(a[j]){re=j;break;}
        if(re==-1){
            f[i]=mi2[i];
            f[i].s[0]--;
            continue;
        }
        f[i]=f[re-1]+mi2[i]-mi2[re];
    }
    f[n].coutt();
    return 0;
}