2 seconds
128 megabytes
standard input
standard output
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 2x MB
memory stick. If Bob had such a stick, he sold it and got 2x berllars. -
Bob won some programming competition and got a 2x 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.
The first input line contains number n (1 ≤ n ≤ 5000)
— amount of Bob's working days. The following nlines 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
/* ID: xinming2 PROG: LANG: C++ */ #include <cstdio> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <map> #include <string> #include <stack> #include <ctype.h> #include <vector> #include <queue> using namespace std; #define MAXN 20010 #define Inf 0x7ffffff #define eps 1e10-8 typedef long long LL; const double PI = cos(-1); typedef double D; //#define Online_Judge #define outstars cout << "***********************" << endl; struct Pair { int x ;///记录该数据是否售出 int y; }a[5050]; int have[2050]; int sell[2050]; int used[5050];///是否用过 int b[1050] , nb; char s[10]; void twice()///2倍后进位 { for(int i = 0 ; i <= nb ; i++) { b[i] <<= 1; } for(int i = 0 ; i < nb ; i++) { if(b[i] > 9) { b[i + 1] += b[i] / 10; b[i] %= 10; } } while(b[nb] > 9) { b[nb + 1] = b[nb] / 10; b[nb] %= 10; nb++; } } void up()///个位开始加以一，进位 { b[0] ++; for(int i = 0 ; i < nb ; i++) { if(b[i] > 9) { b[i + 1] += b[i] / 10; b[i] %= 10; } } while(b[nb] > 9) { b[nb + 1] = b[nb] / 10; b[nb] %= 10; nb++; } } void print() { for(int i = nb ; i >= 0 ; i--) { printf("%d",b[i]); } printf("\n"); } int main() { #ifdef Online_Judge freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif // Online_Judge int x , n , j; while(scanf("%d",&n)!=EOF) { memset(b , 0 , sizeof(b)); nb = 0; // memset(a , 0 , sizeof(a)); memset(used , 0 , sizeof(used)); memset(sell , -1 , sizeof(sell)); for(int i = 0 ; i < n ; i++) { scanf("%s%d",s , &x); if(s[0] =='s') { sell[x] = i; a[i] = (Pair){0 , x}; } else a[i] = (Pair){1 , x}; } for(int i = 2000 ; i >= 0 ; i--) { twice(); if(sell[i] >= 0)///如果卖掉了就去计算收益 { for(j = sell[i] ; j >= 0 ;j--) { if(used[j])break; if(a[j].x == 1&&a[j].y == i)break; } if(j >= 0&&!used[j]) { for(;j <= sell[i] ; j++) { used[j] = 1; } up(); } } } print(); } return 0; }有些麻烦的一道模拟题，但是没什么难点
