本文共 5392 字，大约阅读时间需要 17 分钟。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std; int max(int a,int b){return a>b?a:b;}int map[105][105],dp[105][105];int dir[4][2] = {
  {1,0},{-1,0},{0,1},{0,-1}};class CPoint{public:	int height;	int x;	int y;	friend bool operator < (const CPoint &a,const CPoint &b){		return a.height < b.height;	}}road[10005];int main(int i, int j){//	freopen("input.txt","r",stdin);	char name[100];	int N,R,C;	scanf("%d",&N);	while(N--){		scanf("%s %d %d",name,&R,&C);		int numRoad=0;			for(i=0; i
       
        =0 && dx
        
         =0 && dy
         
          map[road[i].x][road[i].y] && dp[road[i].x][road[i].y]+1>dp[dx][dy]){ dp[dx][dy] = dp[road[i].x][road[i].y]+1; if(dp[dx][dy]>maxRoad) maxRoad = dp[dx][dy]; } } } printf("%s: %d\n",name,maxRoad); } return 0;}
         
        
       
      
     
    
   

10937

25.82%

2970

69.73%

网上查了下，学习了两种打印方式：

最长公共子序列问题，打印路径总结了两个方法，一个是递归指向，就像前面做的01背包问题如：

for(int i = 1; i < n; i ++)        for(int j = 0; j < n-i; j ++)            for(int k = j; k < i+j; k ++)            {                if(k == j)                 {                    f[j][i+j] = f[j][k]+f[k+1][i+j]+A[j][0]*A[k][1]*A[i+j][1];                    part1[j][i+j] = k;//赋值                }                if(f[j][k]+f[k+1][i+j]+A[j][0]*A[k][1]*A[j+i][1] < f[j][i+j])                     {                        f[j][i+j] = f[j][k]+f[k+1][i+j]+A[j][0]*A[k][1]*A[j+i][1];                        part1[j][i+j] = k;//赋值                    }            }

void printpath(int a, int b)//输出{    if(a == b)    {        printf("A%d", a + 1);        return ;    }    printf("(");    printpath(a, part1[a][b]);    printf(" x ");    printpath(part1[a][b] + 1, b);    printf(")");}

例如：

for(int i = 1; i <= cdnum; i ++)        for(int j = 0; j <= tap; j ++)        {            f[i][j] = f[i-1][j];            p[i][j] = j;//赋值            if(j>=num[i]&&f[i-1][j-num[i]]+num[i] > f[i][j])            {                f[i][j] = f[i-1][j-num[i]]+num[i]; p[i][j] = j-num[i];//赋值            }        }

void print(int i, int j)//打印路径{    if(i == 0)        return;    print(i - 1, p[i][j]);    if(p[i][j] < j)        printf("%d ", num[i]);}

这第二种就是今天用到的 赋值遍历打印路径；

for(int i = 1; i <= m; i ++)        for(int j = 1; j <= n; j ++)            if(!strcmp(a[i], b[j]))                 {                    f[i][j] = f[i-1][j-1] + 1;                    p[i][j] = 1;//赋值                }            else if(f[i-1][j]>f[i][j-1])                        {                            f[i][j] = f[i-1][j];                            p[i][j] = 0;//赋值                        }                        else                         {                            f[i][j] = f[i][j-1];                            p[i][j] = -1;//赋值                        }

void print(int i , int j)//输出{    if(!i || !j)        return ;    if(p[i][j] == 1)    {        print(i-1,j-1);        if(flag)      printf(" ");    else      flag = 1;    printf("%s", a[i]);    }    else if(p[i][j] == 0)                print(i-1,j);                else print(i,j-1);}

/*UVa 531	Compromise最长公共子序列打印  */#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;string text1[105],text2[105];int dp[105][105],p[105][105];bool flag;void print(int i,int j){	if(!i || !j)		return ;	if(p[i][j]==1){		print(i-1,j-1);		if(flag)			cout<<" ";		else			flag=true;		cout << text1[i];	}	else if(p[i][j]==0){		print(i-1,j);	}	else		print(i,j-1);}int main(int i,int j){  	freopen("input.txt","r",stdin);	 	int len1,len2;	while(cin>>text1[1]){		len1 = 2;		len2 = 1;		while(cin >> text1[len1]){			if(text1[len1]=="#") break;			++len1;		}		while(cin >> text2[len2]){			if(text2[len2]=="#") break;			++len2;		}		--len1; --len2;		memset(dp,0,sizeof(dp)); 		for(i=1; i<=len1; ++i){			for(j=1; j<=len2; ++j){				if(text1[i]==text2[j]){					dp[i][j] = dp[i-1][j-1]+1;					p[i][j] = 1;				}				else{					if(dp[i-1][j]>dp[i][j-1]){						dp[i][j] = dp[i-1][j];						p[i][j] = 0;					}					else{						dp[i][j] = dp[i][j-1];								p[i][j] = -1;					}				}			}		}		flag=false;		print(len1,len2);		printf("\n");	}	return 0;}
      
     
    
   

  (01背包打印路径)

#include
   
    #include
    
     #define MAXN 10000int track[MAXN];int dp[22][MAXN];int path[22][MAXN];int max(int a,int b){return a>b?a:b;}void print(int i, int j)//打印路径{    if(i == 0)        return;    print(i-1, path[i][j]);    if(path[i][j] < j)        printf("%d ",track[i]);}int main(){	//freopen("input.txt","r",stdin);	int N,t,i,j;	while(scanf("%d %d",&N,&t)!=EOF){		for(i=1; i<=t; ++i)			scanf("%d",&track[i]);		memset(dp,0,sizeof(dp));		memset(path,0,sizeof(path));		for(i=1; i<=t; ++i){			for(j=0; j<=N; ++j){				dp[i][j] = dp[i-1][j];				path[i][j] = j;				if(j>=track[i]&&dp[i-1][j-track[i]]+track[i]>dp[i][j]					&&dp[i-1][j-track[i]]+track[i]<=N){					dp[i][j]=dp[i-1][j-track[i]]+track[i];					path[i][j]=j-track[i];				}			}		}		print(t,N);	 	printf("sum:%d\n",dp[t][N]);	}		return 0;}
    
   

转载地址：http://uuzni.baihongyu.com/