| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
n*m算法,递归输出路径,贴代码#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 505
int n,m,t;
int s1[N],s2[N];
struct node
{
int p,key;
}dp[N][N];
struct P
{
int pre,num;
}p[N*N];
void f(int index)
{
if(index)
{
f(p[index].pre);
printf("%d ",p[index].num);
}
}
void DP()
{
memset(dp,0,sizeof(dp));
int ans=0,mx,i,j,fi,fj,tem,ansk;
t=1;
p[1].pre=0;
for( i=1;i<=n;i++)
{
mx=0; fi=fj=0;
for( j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
tem=dp[i][j].p;
if(mx<tem&&s1[i-1]>s2[j-1])
{
mx=tem;
fi=i,fj=j;
}
if(s1[i-1]==s2[j-1])
{
dp[i][j].p=mx+1;
dp[i][j].key=t;
p[t].num=s1[i-1];
p[t].pre=dp[fi][fj].key;
t++;
}
if(ans<dp[i][j].p)
{
ans=dp[i][j].p;
ansk=dp[i][j].key;
}
}
}
printf("%d\n",ans);
f(ansk);
printf("\n");
}
int main()
{
scanf("%d",&n);
int i;
for( i=0;i<n;i++)
scanf("%d",&s1[i]);
scanf("%d",&m);
for( i=0;i<m;i++)
scanf("%d",&s2[i]);
DP();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator