【JOJ 2491】
【原题链接】
http://acm.jlu.edu.cn/joj/showproblem.php?pid=2491
【题目大意】
输入一组同学的成绩（语文和数学），将同学分级，分级方法为：定义a两科分数一科高于一科高于等于b，则说a的级别应该比b好，每次去除没有比其好的同学作为一级，剩下降级，依次类推。输入学号，输出级数。
也可以用dp，就是根据分数dp：
if(score[i][j]) level[i][j]=(level[i+1][j]>level[i][j+1]?level[i+1][j]:level[i][j+1])+1;
else level[i][j]=level[i+1][j]>level[i][j+1]?level[i+1][j]:level[i][j+1];
这个是状态转移方程。其他想法和第一种方法类似。
【解题思想】
用分数dp，按说的方法，将同学分级。也可以由下到上分级。
[code]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long student[200005][2],score[410][410],level[410][410];
int main()
{
long caseNum,stuNum,i,j,l,m,testNum,stuID;
scanf("%ld",&caseNum);
while(caseNum--)
{
scanf("%ld",&stuNum);
memset(score,0,sizeof(score));
for(i=0;i<stuNum;i++)
{
scanf("%ld%ld",&student[i][0],&student[i][1]);
score[student[i][0]][student[i][1]]++;
}
l=0;
while(stuNum)
{
m=-1;
l++;
for(i=400;i>=0;i--)
{
for(j=400;j>m;j--)
{//实际上用分数遍历，找到有该分且同级的同学。
if(score[i][j])
{
m=j;
stuNum-=score[i][j];
level[i][j]=l;
score[i][j]=0;
break;
}
}
}
}
scanf("%ld",&testNum);
while(testNum--)
{
scanf("%ld",&stuID);
printf("%ld\n",level[student[stuID][0]][student[stuID][1]]);
}
}
return 0;
}
[\code]