`
king_tt
  • 浏览: 2109077 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

UVA DP入门专题（二）最长公共子序列 打印方法

 
阅读更多


10285-Longest Run on a Snowboard		 4910
55.11%
 2036
93.76%
10075943 10285 Longest Run on a Snowboard Accepted C++ 0.024 2012-05-05 02:12:46
滑雪， 变相的最长递减子序列，它不是求一行的最长递增子序列，而是求在一个方阵，可以往上下左右四个方向走的最长递减路线。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
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<R; ++i){
			for(j=0; j<C; ++j){
				scanf("%d",&map[i][j]);
				road[numRoad].height=map[i][j];
				road[numRoad].x=i;
				road[numRoad].y=j;
				++numRoad;
			}
		}
		
		sort(road,road+numRoad);
	//	memset(dp,1,sizeof(dp));   /* 不能用这个，无法初始化为1 */
		for(i=0; i<R; ++i){
			for(j=0; j<C; ++j)
			 dp[i][j]=1;
		}
 
		int maxRoad = 0;

		for(i=0; i<numRoad; ++i){
			for(j=0; j<4; ++j){
				int dx=road[i].x+dir[j][0];
				int dy=road[i].y+dir[j][1];
				if(dx>=0 && dx<R && dy>=0 && dy<C && map[dx][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;
}




FILE 531-Compromise 10937
25.82%
 2970
69.73%
10076491 531 Compromise Accepted C++ 0.032 2012-05-05 06:18:21
10076471 531 Compromise Wrong answer C++ 0.008 2012-05-05 06:09:26
10076428 531 Compromise Wrong answer C++ 0.012 2012-05-05 05:55:44
10076234 531 Compromise Wrong answer C++ 0.032 2012-05-05 04:32:16
10076222 531 Compromise Wrong answer C++ 0.012 2012-05-05 04:23:57
10076212 531 Compromise Compilation error C++ 0.000 2012-05-05 04:22:35
这题WA了多次，原因在于不懂的打印出 最长公共子序列。

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

最长公共子序列问题，打印路径总结了两个方法，一个是递归指向，就像前面做的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<iostream>
#include<string>
#include<cstring>
#include<cstdio>
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;
}











624-CD
 (01背包打印路径)




#include<cstdio>
#include<cstring>
#define MAXN 10000

int 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://blog.csdn.net/shuangde800，By
  D_Double














  


  

    
    
分享到：
      
      
    

  


  

    

      
      |
      Java 类的生命周期详解
    

  

  

        
  

    
  

    
评论

    
    
    
    
  


  

    
发表评论

            
   您还没有登录,请您登录后再发表评论 

      

  

  





  

    
相关推荐

    
    
  





  
    Magicbox
  













      

            
    

    
    
  

  



   Global site tag (gtag.js) - Google Analytics