Description
Last year Bob earned by selling memory sticks. During each of n
- A customer came to Bob and asked to sell him a 2x MB memory stick. If Bob had such a stick, he sold it and got 2x
- Bob won some programming competition and got a 2x
Bob never kept more than one memory stick, as he feared to mix up their capacities, and deceive a customer unintentionally. It is also known that for each memory stick capacity there was at most one customer, who wanted to buy that memory stick. Now, knowing all the customers' demands and all the prizes won at programming competitions during the last n
Input
The first input line contains number n (1 ≤ n ≤ 5000) — amount of Bob's working days. The following n lines contain the description of the days. Line sell x stands for a day when a customer came to Bob to buy a 2x MB memory stick (0 ≤ x ≤ 2000). It's guaranteed that for each x there is not more than one line sell x. Line win x stands for a day when Bob won a 2x MB memory stick (0 ≤ x ≤ 2000).
Output
Output the maximum possible earnings for Bob in berllars, that he would have had if he had known all the events beforehand. Don't forget, please, that Bob can't keep more than one memory stick at a time.
Sample Input
Input
7
win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10 Output
1056
Input
3
win 5
sell 6
sell 4 Output
简单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, 0, 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;
}