UVA.10066 The Twin Towers (DP LCS)

2019-11-08 19:45:38

字体：大中小

来源：转载

供稿：网友

UVA.10066 The Twin Towers (DP LCS)

题意分析

有2座塔，分别由不同长度的石块组成。现在要求移走一些石块，使得这2座塔的高度相同，求高度最大是多少。

问题的实质可以转化为LCS（最长公共子序列）问题。推荐一篇写的比较好的博文：动态规划求解最长公共子序列（LCS）

核心的状态转移方程： if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] +1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

代码总览

/* Title:UVA.10066 Author:pengwill Date:2017-2-16*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 105using namespace std;int a[nmax],b[nmax],dp[nmax][nmax];int main(){ //freopen("in.txt","r",stdin); int n,m,cas = 0; while(scanf("%d%d",&n,&m) && (n||m)){ PRintf("Twin Towers #%d/nNumber of Tiles : ",++cas); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i = 1;i <=n; ++i) scanf("%d",&a[i]); for(int i = 1;i <=m; ++i) scanf("%d",&b[i]); for(int i = 1; i<=n; ++i) for(int j = 1; j<=m;++j){ if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] +1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } printf("%d/n/n",dp[n][m]); } return 0;}

上一篇：UVA.10130 SuperSale (DP 01背包)

下一篇：UVA.562 Dividing coins (DP 01背包)