Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

n*m算法,递归输出路径,贴代码

Posted by sanyaocangku at 2012-08-16 16:33:13 on Problem 2127
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator