http://codeforces.com/problemset/problem/18/D
Last year Bob earned by selling memory sticks. During each of n days of his work one of the two following events took place:
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 days, Bob wants to know, how much money he could have earned, if he had acted optimally.
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 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.
7 win 10 win 5 win 3 sell 5 sell 3 win 10 sell 10
1056
3 win 5 sell 6 sell 4
0
/**
CF 18D 高精度+贪心
题目大意：一个人可以得到2^x的内存，可以卖出2^x的内存换取，2^x的钱，win代表得到，sell代表卖出。但是这个人手中任意时刻只能有一块内存，
问怎么安排能使获得的钱最多。
解题思路：因为题目中有明确的说明，每种内存最多只能卖一次，所以所有小于x的2的幂加起来也没有2^x大，可以采用贪心，sell从大到小排序，优先处理
数字略大，要用到高精度
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=5005;
int f[maxn][maxn],ans[maxn],a[maxn];
char s[15];
int n;
int main()
{
///预处理出2的0~2000次方
memset(f,0,sizeof(f));
f[0][0]=1;
f[0][1]=1;
for(int i=1; i<2003; i++)
{
int tt=0;
for(int j=1; j<=f[i-1][0]; j++)
{
f[i][j]=f[i-1][j]+f[i-1][j]+tt;
tt=f[i][j]/10;
f[i][j]%=10;
++f[i][0];
}
if(tt)
f[i][++f[i][0]]=tt;
/*printf("%d ",i);
for(int k=f[i][0];k>=1;k--)
printf("%d",f[i][k]);
printf("\n");
getchar();*/
}
while(~scanf("%d",&n))
{
vector <pair<int,int> >b;
for(int i=0; i<n; i++)
{
scanf("%s%d",s,&a[i]);
if(s[0]=='s')
b.push_back(make_pair(a[i],i)),a[i]=-1;
}
sort(b.rbegin(),b.rend());
memset(ans,0,sizeof(ans));
ans[0]=1;
for(int i=0; i<b.size(); i++)
{
int x=b[i].first;
int y=b[i].second;
for(int j=y-1; j>=0&&a[j]!=-2; j--)
{
if(a[j]==x)
{
int tt=0;
// printf("(%d)\n",a[j]);
int bit=max(ans[0],f[x][0]);
for(int k=1; k<=bit; k++)
{
ans[k]+=f[x][k]+tt;
tt=ans[k]/10;
ans[k]%=10;
}
if(tt)ans[++bit]+=tt;
ans[0]=bit;
for(int k=j; k<=y; k++)
a[k]=-2;
break;
}
}
}
for(int i=ans[0]; i>=1; i--)
{
printf("%d",ans[i]);
}
printf("\n");
}
return 0;
}
原文：http://blog.csdn.net/lvshubao1314/article/details/42394577