Codeforces 18D

简单dp，对于每个sell找到最近的对应win，更新即可，输出要用高精度。

#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long LL;
const int low(int x){
    return x & - x;
}
const int mod = 51123987;
const int maxn = 5e3 + 10;
int n,x,pre[maxn];
char s[maxn];
bitset<2005> dp[maxn],y;
vector<int> ans;

int main(){
    while(~scanf("%d",&n)){
        memset(pre,sizeof( pre ));
        dp[0] = 0;  ans.clear();
        for(int i = 1 ; i <= n ; i++){
            scanf("%s%d",s,&x);
            if(s[0] == 'w'){
                pre[x] = i; dp[i] = dp[i - 1];
            } else {
                if(!pre[x]) dp[i] = dp[i - 1];
                else {
                    y = dp[pre[x] - 1];
                    y[x] = 1;
                    for(int j = 2000 ; j >= 0 ; j--){
                        if(dp[i - 1][j] > y[j]){
                            dp[i] = dp[i - 1]; break;
                        }
                        if(dp[i - 1][j] < y[j]){
                            dp[i] = y; break;
                        }
                        if(j == 0) dp[i] = y;
                    }
                }
            }
        }
        ans.push_back(0);
        for(int i = dp[n].size() - 1 ; i >= 0 ; i--){
            int k = 0;
            for(int j = 0 ; j < ans.size() ; j++){
                int now = ans[j];
                ans[j] = ( now * 2 + k ) % 10;
                k = ( now * 2 + k ) / 10;
            }
            if(k) ans.push_back(k);
            if(dp[n][i]){
                k = 0; ans[0]++;
                for(int j = 0 ; j < ans.size() ; j++){
                    int now = ans[j];
                    ans[j] = ( now + k ) % 10;
                    k = ( now + k ) / 10;
                }
            }
        }
        for(int i = ans.size() - 1 ; i >= 0 ; i--) printf("%d",ans[i]);
        printf("n");
    }
    return 0;
}