注:连不上UVA,还没有AC,所以仅作为参考
动态规划题,根据学生给的历史事件的顺序,与正确的历史事件顺序进行比较,找出其中最长的递增序列,可以参考编程之美中关于最长递增序列的解答。在输入测试数据的时候,处理一下数据。
输入:第一行是正确的事件顺序,接下来为学生的答案
10
3 1 2 4 9 5 10 6 8 7//意思是:1事项在第三个时间位置发生,2事项在第一个时间发生以此类推:转化为:2 3 1 4 6 8 10 9 5 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6
输出:依次输出每个case 的答案
代码:
#include <stdio.h>
#include <memory.h>
int count(int *cas,int letters_num){
int lis[20],i,j,MAX=0;
memset(lis,0,20*sizeof(int));
for (i=0;i<letters_num;i++)//外层循环遍历n遍
{
lis[i]=1;
for (j=0;j<i;j++)//内层循环遍历i遍
{
if (cas[i]>cas[j]&&lis[j]+1>lis[i])//满足动态规划的条件,即前面的状态不会影响到后面的状态
{
lis[i]=lis[j]+1;
}
}
}
for(i=0;i<letters_num;i++){
if (MAX<lis[i])
{
MAX=lis[i];
}
}
return MAX;
}
int main(){
#ifdef TEST
freopen("test.txt","r",stdin);
freopen("tout.txt","w",stdout);
#endif
int letters_num;
int right_order[20];
int cas[20];
scanf("%d\n",&letters_num);
int i=0,j=0,b,score;
char a;
for (i=0;i<letters_num;i++)
{
scanf("%d",&right_order[i]);
getchar();
}
i=0;
while(scanf("%d",&b)==1){
for (j=0;j<letters_num;j++)
{
if (b==right_order[j])//找出该事件在正确顺序中的位置
{
cas[i++]=j;
break;
}
}
a=getchar();
if (a=='\n')
{
i=0;
score=count(cas,letters_num);
printf("%d\n",score);
}
}
return 0;
}