题目

{% raw %}

点击显/隐题目
{% endraw %} Finally term begins. luras loves school so much as she could skip the class happily again.(wtf?)

Luras will take n lessons in sequence(in another word, to have a chance to skip xDDDD).

For every lesson, it has its own type and value to skip.

But the only thing to note here is that luras can't skip the same type lesson more than twice.

Which means if she have escaped the class type twice, she has to take all other lessons of this type.

Now please answer the highest value luras can earn if she choose in the best way.

{% raw %}



{% endraw %}

The first line is an integer T which indicates the case number.

And as for each case, the first line is an integer n which indicates the number of lessons luras will take in sequence.

Then there are n lines, for each line, there is a string consists of letters from 'a' to 'z' which is within the length of 10,
and there is also an integer which is the value of this lesson.

The string indicates the lesson type and the same string stands for the same lesson type.

It is guaranteed that——

T is about 1000

For 100% cases, 1 <= n <= 100，1 <= |s| <= 10, 1 <= v <= 1000

{% raw %}



{% endraw %}

As for each case, you need to output a single line.
there should be 1 integer in the line which represents the highest value luras can earn if she choose in the best way.

{% raw %}





{% endraw %}

2
5
english 1
english 2
english 3
math 10
cook 100
2
a 1
a 2

{% raw %}



{% endraw %}

115
3

{% raw %}




{% endraw %}

题解

跳过一定数目的课程,使最后得到的总值最多
同一门课最多跳过两次

因此,将每一门课 value 最高的两门选出来加起来即可

用一个结构体维护所有的课程,根据课程名称和 value 排序即可

代码

点击显/隐代码
```cpp Skip the Class https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include using namespace std;

const int maxn = 105;

struct Node{
string name;
int value;
bool operator < (const Node rhs)const{
if(name == rhs.name)
return value > rhs.value;
return name < rhs.name;
}
};

Node node[maxn];

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;
while(T--){
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> node[i].name >> node[i].value;
    sort(node,node+n);

    string ls = "";
    int cnt = 0;
    int ans = 0;
    for(int i=0;i<n;i++){
        if(ls == node[i].name){
            if(cnt == 2){
                continue;
            }else{
                cnt++;
                ans += node[i].value;
            }
        }else{
            ls = node[i].name;
            cnt = 1;
            ans += node[i].value;
        }


    }
    cout << ans<<endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>