设为首页 加入收藏

TOP

UVa 531: Compromise
2014-11-23 21:42:21 来源: 作者: 【 】 浏览:12
Tags:UVa 531: Compromise
求最长公共子序列(LCS)并打印序列。dp解决,各节点标记最终的序列选择,最后递归打印即可。
我的解题代码如下:
 
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define max(a,b) (a>b a:b)  
#define WORDLEN 32  
#define SENTENCELEN 102  
char P1[SENTENCELEN][WORDLEN], P2[SENTENCELEN][WORDLEN];  
int dp[SENTENCELEN][SENTENCELEN];  
int PathSel[SENTENCELEN][SENTENCELEN];  
  
void PrintSeq(int i, int j)  
{  
    if(i<0 || j<0 || !dp[i][j]) return ;  
    if(!PathSel[i][j])  
    {  
        PrintSeq(i-1,j-1);  
        if(dp[i][j]==1) cout << P1[i];  
        else cout << ' ' << P1[i];  
    }  
    else if(PathSel[i][j]==1) PrintSeq(i-1,j);  
    else PrintSeq(i,j-1);     
}  
int main()  
{  
    int m,n;  
    while(cin >> P1[0])  
    {  
        m = 0, n = 0;  
        while(P1[m++][0]!='#' && cin >> P1[m]) ; m--;  
        while(cin >> P2[n] && P2[n++][0]!='#') ; n--;  
          
        dp[0][0] = 0;  
        for(int i=0; i dp[i][j-1])  
                {  
                    dp[i][j] = dp[i-1][j];  
                    PathSel[i][j] = 1;  
                }  
                else  
                {  
                    dp[i][j] = dp[i][j-1];  
                    PathSel[i][j] = 2;  
                }  
            }  
        }  
        PrintSeq(m-1,n-1);  
        cout << endl;  
    }  
    return 0;  
}  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇ural 1869. New Year Cruise 下一篇poj 3107 Godfather(树形dp)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·【C语言】动态内存管 (2025-12-27 06:23:20)
·C语言中的内存管理 - (2025-12-27 06:23:16)
·C语言指南:C语言内 (2025-12-27 06:23:14)
·Redis on AWS:Elast (2025-12-27 04:19:30)
·在 Spring Boot 项目 (2025-12-27 04:19:27)