Lotus and Characters

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/131072 K (Java/Others) Total Submission(s): 1199    Accepted Submission(s): 409 Problem Description Lotus has  n  kinds of characters,each kind of characters has a value and a amount.She wants to construct a string using some of these characters.Define the value of a string is:its first character's value*1+its second character's value *2+...She wants to calculate the maximum value of string she can construct. Since it's valid to construct an empty string,the answer is always  ≥0 。   Input First line is  T(0≤T≤1000)  denoting the number of test cases. For each test case,first line is an integer  n(1≤n≤26) ,followed by  n  lines each containing 2 integers  vali,cnti(|vali|,cnti≤100) ,denoting the value and the amount of the ith character.   Output For each test case.output one line containing a single integer,denoting the answer.   Sample Input 2 2 5 1 6 2 3 -5 3 2 1 1 1   Sample Output 35 5   Source BestCoder Round #91   Recommend jiangzijing2015   |   We have carefully selected several similar problems for you:   6018  6017  6016  6015  6014  #include <iostream> #include<math.h> #include<algorithm> #include<memory.h> using namespace std; long long int a[7000000]; long long int Maxn(long long int n,long long int a[]) { long long int max1=-1000000,t=1,sum; for(int i=1;i<=n;i++) { sum=0; t=1; for(int j=n-i;j<n;j++)//到着从最后开始数，假如只有一个数，取最后一个，假如只有两个数，取最后一个和倒数第二个 { sum=sum+t*a[j]; t++; } if(max1<sum) max1=sum; if(sum<0) break; //Since it's valid to construct an empty string,the answer is always ≥0。 //这句是说，如果输入的全是负数的话，输出0,坑死啦。。。 } if(max1<0) cout<<0<<endl; else cout<<max1<<endl; } int main(void) { int num; cin>>num; while(num--) { long long int n,k=0,x,y; cin>>n; for(int i=0;i<n;i++) { cin>>x>>y; while(y--) { a[k++]=x; } } sort(a,a+k);//从小到大排序 Maxn(k,a); } return 0; }