2014
03-06

# Awesome DJMAX

CD is an Otaku, he likes to play PSP game, and his favorite game is DJMAX. In this game, the player will listen to the music, then many notes will appear on the screen and fall down from the top. When the notes move to the line on the button of the screen, the player should press the correct keys just on time, and the system will judge your rate and give scores.
Every time after he finishes one mission, he always doubts the Score System of that game, he thinks he should get more points. Now he turns to you for help, can you write an impartial Score System so that tell him how many points he actually can get.
The rule of your Score System is:
a) There are three results CD may get: “COOL”, “GOOD”, “MISS”.
b) Each “COOL” will give CD 100 points; Each “GOOD” will give CD 50 points; Each “MISS” give CD 0 points.
c) Each “COOL” will give CD 1/10 “MAX-value”; Each “GOOD” will give CD 1/20 “MAX-value”. After CD gets one “MAX-value” or more, every “MAX-value” will add extra 10 scores to every “COOL” and 5 to every “GOOD”.
d) If CD beats notes incessantly, he will get COMBO. 2 notes will be 2 COMBO, 3 notes will be 3 COMBO, and so on. But, if he misses one note, the COMBO will back to zero, and all the “MAX-value” he have will be lost.

The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of an integers N(N<=1000), indicating the number of notes.
Then N lines follow, each line contains a string, this string will be “COOL”, “GOOD” or “MISS”.

The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of an integers N(N<=1000), indicating the number of notes.
Then N lines follow, each line contains a string, this string will be “COOL”, “GOOD” or “MISS”.

1
20
COOL
COOL
COOL
GOOD
GOOD
GOOD
GOOD
COOL
COOL
COOL
COOL
COOL
COOL
COOL
MISS
COOL
MISS
MISS
GOOD
COOL

1470

#include<stdio.h>
int main()
{
int t,s,i,pc,pg,n;
char a,b,c,d;
int v;
scanf("%d",&t);
while(t–)
{
s=0;
pc=100;
pg=50;
v=0;
scanf("%d",&n);
getchar();
for(i=1;i<=n;i++)
{
scanf("%c%c%c%c",&a,&b,&c,&d);
getchar();
if(a==’C')
{
s=s+pc;
v=v+2;
pc=100+10*(v/20);
pg=50+5*(v/20);
}
else if(a==’G')
{
s=s+pg;
v=v+1;
pg=50+5*(v/20);
pc=100+10*(v/20);

}
else if(a==’M')
{
v=0;
pc=100;
pg=50;
}
}
printf("%d\n",s);
}
return 0;
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。