开始练习DP的第一题，受挫，无语。
主要在于输入数据的格式弄得我很不习惯，输入的并不是答案或者学生填写结果的顺序。
最长公共子序列问题，也可以最长上升子序列来做。
以下是我的代码：
#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(27);
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int n;
scanf("%d",&n);
int ans[kMaxn];
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
ans[t]=i;
}
cin.get();
string line;
while(getline(cin,line))
{
istringstream sin(line);
int r[kMaxn];
for(int i=1;i<=n;i++)
{
int t;
sin>>t;
r[t]=find(ans+1,ans+n+1,i)-ans;
}
int len(0),d[kMaxn]={0};
for(int i=1;i<=n;i++)
{
if(r[i]>d[len])
{
len++;
d[len]=r[i];
}
else
{
int pos=lower_bound(d+1,d+len+1,r[i])-d;
d[pos]=r[i];
}
}
printf("%d\n",len);
}
return 0;
}
posted on 2011-05-24 08:15
lee1r 阅读(437)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划