cf18D Seller Bob （线性DP_好题）

题意：

题目告诉你你能够按顺序获得一些价值为2^x的硬盘，你可以保留一个并且在之后的几天卖掉，但是你在卖掉当前这个之前是不能保留其他的硬盘的，在已经知道什么时候会有人买什么类型的硬盘的前提下，问你能获得的最大收益是多少。

dp[i]表示当前i个序列中能获得的最大值... pre[t] 维护内存为t的最近的序列....最后用高精度即可

Last year Bob earned by selling memory sticks. During each of n days of his work one of the two following events took place:

• A customer came to Bob and asked to sell him a 2^x MB memory stick. If Bob had such a stick, he sold it and got 2^x berllars.
• Bob won some programming competition and got a 2^x MB memory stick as a prize. Bob could choose whether to present this memory stick to one of his friends, or keep it.

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.

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 2^x 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 2^x 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

7
win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10

1056

3
win 5
sell 6
sell 4

0

#include 
#include 
#include 
#include
#include 
using namespace std; #define MAXN 9999
#define MAXSIZE 10
#define DLEN 4class BigNum
{ 
private: int a[500];    //????????? int len;       //????
public: BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //????BigNum(const int);       //???int??????????BigNum(const char*);     //????????????????BigNum(const BigNum &);  //??????BigNum &operator=(const BigNum &);   //???????,??????????friend istream& operator>>(istream&,  BigNum&);   //???????friend ostream& operator<<(ostream&,  BigNum&);   //???????BigNum operator+(const BigNum &) const;   //???????,??????????? BigNum operator-(const BigNum &) const;   //???????,??????????? BigNum operator*(const BigNum &) const;   //???????,??????????? BigNum operator/(const int   &) const;    //???????,?????????????BigNum operator^(const int  &) const;    //???n????int    operator%(const int  &) const;    //?????int???????????    bool   operator>(const BigNum & T)const;   //?????????????bool   operator>(const int & t)const;      //?????int??????????void print();       //????
}; 
BigNum::BigNum(const int b)     //???int??????????
{ int c,d = b;len = 0;memset(a,0,sizeof(a));while(d > MAXN){c = d - (d / (MAXN + 1)) * (MAXN + 1); d = d / (MAXN + 1);a[len++] = c;}a[len++] = d;
}
BigNum::BigNum(const char*s)     //????????????????
{int t,k,index,l,i;memset(a,0,sizeof(a));l=strlen(s);   len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-1;i>=0;i-=DLEN){t=0;k=i-DLEN+1;if(k<0)k=0;for(int j=k;j<=i;j++)t=t*10+s[j]-'0';a[index++]=t;}
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //??????
{ int i; memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++)a[i] = T.a[i]; 
} 
BigNum & BigNum::operator=(const BigNum & n)   //???????,??????????
{int i;len = n.len;memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++) a[i] = n.a[i]; return *this; 
}
istream& operator>>(istream & in,  BigNum & b)   //???????
{char ch[MAXSIZE*4];int i = -1;in>>ch;int l=strlen(ch);int count=0,sum=0;for(i=l-1;i>=0;){sum = 0;int t=1;for(int j=0;j<4&&i>=0;j++,i--,t*=10){sum+=(ch[i]-'0')*t;}b.a[count]=sum;count++;}b.len =count++;return in;}
ostream& operator<<(ostream& out,  BigNum& b)   //???????
{int i;  cout << b.a[b.len - 1]; for(i = b.len - 2 ; i >= 0 ; i--){ cout.width(DLEN); cout.fill('0'); cout << b.a[i]; } return out;
}BigNum BigNum::operator+(const BigNum & T) const   //???????????
{BigNum t(*this);int i,big;      //??   big = T.len > len ? T.len : len; for(i = 0 ; i < big ; i++) { t.a[i] +=T.a[i]; if(t.a[i] > MAXN) { t.a[i + 1]++; t.a[i] -=MAXN+1; } } if(t.a[big] != 0)t.len = big + 1; elset.len = big;   return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //??????????? 
{  int i,j,big;bool flag;BigNum t1,t2;if(*this>T){t1=*this;t2=T;flag=0;}else{t1=T;t2=*this;flag=1;}big=t1.len;for(i = 0 ; i < big ; i++){if(t1.a[i] < t2.a[i]){ j = i + 1; while(t1.a[j] == 0)j++; t1.a[j--]--; while(j > i)t1.a[j--] += MAXN;t1.a[i] += MAXN + 1 - t2.a[i]; } elset1.a[i] -= t2.a[i];}t1.len = big;while(t1.a[t1.len - 1] == 0 && t1.len > 1){t1.len--; big--;}if(flag)t1.a[big-1]=0-t1.a[big-1];return t1; 
} BigNum BigNum::operator*(const BigNum & T) const   //??????????? 
{ BigNum ret; int i,j,up; int temp,temp1;   for(i = 0 ; i < len ; i++){ up = 0; for(j = 0 ; j < T.len ; j++){ temp = a[i] * T.a[j] + ret.a[i + j] + up; if(temp > MAXN){ temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); ret.a[i + j] = temp1; } else{ up = 0; ret.a[i + j] = temp; } } if(up != 0) ret.a[i + j] = up; } ret.len = i + j; while(ret.a[ret.len - 1] == 0 && ret.len > 1)ret.len--; return ret; 
} 
BigNum BigNum::operator/(const int & b) const   //?????????????
{ BigNum ret; int i,down = 0;   for(i = len - 1 ; i >= 0 ; i--){ ret.a[i] = (a[i] + down * (MAXN + 1)) / b; down = a[i] + down * (MAXN + 1) - ret.a[i] * b; } ret.len = len; while(ret.a[ret.len - 1] == 0 && ret.len > 1)ret.len--; return ret; 
}
int BigNum::operator %(const int & b) const    //?????int???????????    
{int i,d=0;for (i = len-1; i>=0; i--){d = ((d * (MAXN+1))% b + a[i])% b;  }return d;
}
BigNum BigNum::operator^(const int & n) const    //???n????
{BigNum t,ret(1);int i;if(n<0)exit(-1);if(n==0)return 1;if(n==1)return *this;int m=n;while(m>1){t=*this;for( i=1;i<<1<=m;i<<=1){t=t*t;}m-=i;ret=ret*t;if(m==1)ret=ret*(*this);}return ret;
}
bool BigNum::operator>(const BigNum & T) const   //?????????????
{ int ln; if(len > T.len)return true; else if(len == T.len){ ln = len - 1; while(a[ln] == T.a[ln] && ln >= 0)ln--; if(ln >= 0 && a[ln] > T.a[ln])return true; elsereturn false; } elsereturn false; 
}
bool BigNum::operator >(const int & t) const    //?????int??????????
{BigNum b(t);return *this>b;
}void BigNum::print()    //????
{ int i;   cout << a[len - 1]; for(i = len - 2 ; i >= 0 ; i--){ cout.width(DLEN); cout.fill('0'); cout << a[i]; } cout << endl;
}
BigNum dp[5555],num[2222];
int pre[5555];
char s[11];
int main(void)
{int i,n,j,t;num[0]=1;for(i=1;i<=2000;i++) num[i]=num[i-1]*2;scanf("%d",&n);for(i=1;i<=n;i++) {scanf("%s%d",s,&t);dp[i]=dp[i-1];if(s[0]=='w') pre[t]=i;else {if(pre[t]) {BigNum tem = dp[pre[t]]+num[t];if(tem>dp[i]) dp[i]=tem;}}}dp[n].print();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！