# Skip the Class

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 401    Accepted Submission(s): 235

Problem Description

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.

Input

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

Output

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.

Sample Input

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

Sample Output

```115
3

#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <string>
#include <vector>

using namespace std;
map<string,int> m;
string s;
int value;
int n;
vector<int> v[105];
int main()
{
int t;
scanf("%d",&t);
int ans=0;
while(t--)
{
scanf("%d",&n);
int cot=0;
ans=0;
m.clear();
for(int i=1;i<=n;i++)
v[i].clear();
for(int i=1;i<=n;i++)
{
cin>>s>>value;
if(!m[s]) m[s]=++cot;
v[m[s]].push_back(value);
}
for(int i=1;i<=cot;i++)
sort(v[i].begin(),v[i].end());
for(int i=1;i<=cot;i++)
{
int l=v[i].size()-1;
ans+=v[i][l];
if(l>=1)
ans+=v[i][l-1];
}
printf("%d\n",ans);
}
return 0;
}```

0 条评论

• ### ZOJ 3715 Kindergarten Election

At the beginning of the semester in kindergarten, the n little kids (indexed fro...

• ### PAT 1008 Elevator

1008. Elevator (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 ...

1006. Sign In and Sign Out (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 1600...

• ### 【PAT甲级】Friend Numbers

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### cf1000F. One Occurrence(线段树 set)

首先把询问离线，预处理每个数的\(pre, nxt\)，同时线段树维护\(pre\)(下标是\(pre\)，值是\(i\))，同时维护一下最大值

• ### #628 DIV2 题解

组样例，每组给一个和个数 。将同一个序列重复次得到一个新序列，问可以从新序列中严格最长上升子序列长度为多少。

• ### 09-排序3 Insertion or Heap Sort (25分)

Insertion sort iterates, consuming one input element each repetition, and growin...

• ### 395. Longest Substring with At Least K Repeating Characters

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元...

• ### LeetCode 75. Sort Colors题目分析

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0，1 和 2 分别代...

• ### P3183 [HAOI2016]食物链

题目描述 如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形...