hdu----Lotus and Characters

深碍√TFBOYSˉ_ 2022-06-15 01:24 170阅读 0赞

问题描述

Lotus有$n$种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。
    定义串的价值为：第1位字母的价值*1+第2位字母的价值*2+第3位字母的价值*3……
    求Lotus能构造出的串的最大价值。（可以构造空串，因此答案肯定$\geq 0$）

输入描述

第一行是数据组数$T(0 \leq T \leq 1000)$。
    对于每组数据，第一行一个整数$n(1 \leq n \leq 26)$，接下来$n$行，每行2个整数$val_i,cnt_i(|val_i|,cnt_i\leq 100)$，分别表示第$i$种字母的价值和个数限制。

输出描述

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

输入样例

2
    2
    5 1
    6 2
    3
    -5 3
    2 1
    1 1

输出样例

35
    5

就是个累加的问题，思维技巧题

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int a[100000];
    int main()
    {
        int T,n,b,num;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            int i = 0,j;
            while(n--)
            {
                scanf("%d %d",&b,&num);
                while(num--)
                    a[i++]=b;
            }
            sort(a,a+i);
            int sum = 0,ans = 0;
            for(j = i-1; j >= 0; j--)
            {
                sum = sum + a[j];
                if(sum < 0)
                    break;
                ans += sum;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

Lotus has  n![Image 1][] 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![Image 1][]。

Inpu

First line is  T(0≤T≤1000)![Image 1][] denoting the number of test cases.  
For each test case,first line is an integer  n(1≤n≤26)![Image 1][],followed by  n![Image 1][] lines each containing 2 integers  val![Image 1][]i![Image 1][],cnt![Image 1][]i![Image 1][](|val![Image 1][]i![Image 1][]|,cnt![Image 1][]i![Image 1][]≤100)![Image 1][],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

[Image 1]: