POJ 2127 最长公共上升子序列

动态规划法:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1004
#define MN 1008
#define INF 100000007
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
int n1,n2,a[MM],b[MM];//a,b序列及其长度
int dp[MM][MM],pre[MM][MM],lcis[MM];//lcis为最长公共上升子序列
int ans=-1;//ans为最长公共上升子序列长度
void getLcis()
{
int x=n1,y=0,cnt=1,i,j,k;
mem(dp,0),mem(pre,0);
for(i=1;i<=n1;i++)
{
k=0;
for(j=1;j<=n2;j++)
{
if(a[i]!=b[j]) dp[i][j]=dp[i-1][j];
if(a[i]>b[j]&&dp[i][j]>dp[i][k]) k=j;
if(a[i]==b[j]) dp[i][j]=dp[i][k]+1,pre[i][j]=k;
}
}
for(i=1;i<=n2;i++)
if(dp[n1][i]>ans) ans=dp[n1][i],y=i;
while(dp[x][y])
{
if(a[x]!=b[y]) x--;
else lcis[ans-cnt]=b[y],cnt++,y=pre[x][y];
}
}
int main()
{
sca(n1);
for(int i=1;i<=n1;i++)
sca(a[i]);
sca(n2);
for(int i=1;i<=n2;i++)
sca(b[i]);
getLcis();
pri(ans);
for(int i=0;i<ans;i++)
printf("%d ",lcis[i]);
puts("");
return 0;
}
上一篇:Oracle主键自增的实现


下一篇:【转】nginx服务器安装及配置文件详解