Best Coder Lotus and Characters

Lotus and Characters

问题描述

Lotus有nn种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。

定义串的价值为：第1位字母的价值*1+第2位字母的价值*2+第3位字母的价值*3……

求Lotus能构造出的串的最大价值。（可以构造空串，因此答案肯定geq 0≥0）

输入描述

第一行是数据组数T(0 leq T leq 1000)T(0≤T≤1000)。

对于每组数据，第一行一个整数n(1 leq n leq 26)n(1≤n≤26)，接下来nn行，每行2个整数val_i,cnt_i(|val_i|,cnt_ileq 100)vali,cnti(∣vali∣,cnti≤100)，分别表示第ii种字母的价值和个数限制。

输出描述

对于每组数据，输出一行一个整数，表示答案。

输入样例

5 1

6 2

-5 3

2 1

1 1

输出样例

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <string>
10 #include <cstring>
11 using namespace std;
12 struct node {int x,y;} t[105];// x-价值  y-个数限制 
13 int a[100005],ans,T,n,cnt,MAX,S,sum;
14 int main()
15 {
16     scanf("%d",&T);
17     while (T--)
18     {
19         scanf("%d",&n);
20         for (int i=1; i<=n; i++)
21         {
22             scanf("%d%d",&t[i].x,&t[i].y);
23             while (t[i].y--) a[++cnt]=t[i].x;//a处理处一个序列
24             //价值的全排列 
25         }
26         MAX=0;
27         sort(a+1,a+cnt+1);
28         for (int i=cnt; i>=1; i--) {sum+=a[i]; S+=sum; MAX=max(MAX,S);} 
29         /*从后往前推 其中肯定会有到负数的 情况
30         这时我们考虑 若在其前添加一个负数， 他后面的数都会多乘一个1
31         相当于多加了自身一遍，所以我们使sum维护一个和，S 
32         维护前缀和 如果说S大于这个负数 那么就加上这个负数 
33         */ 
34         printf("%d
",MAX);
35         ans=cnt=MAX=sum=S=0;
36     }
37     return 0;
38 }

人生第一次在BestCoder打比赛。。15分钟AC