開始練習(xí)DP的第一題，受挫，無語。
主要在于輸入數(shù)據(jù)的格式弄得我很不習(xí)慣，輸入的并不是答案或者學(xué)生填寫結(jié)果的順序。
最長公共子序列問題，也可以最長上升子序列來做。
以下是我的代碼：
#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 閱讀(483)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃