【UVA】10066-The Twin Towers（最长公共子串问题）

本文主要是介绍【UVA】10066-The Twin Towers（最长公共子串问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

赤裸裸的最长公共子串问题，没什么好说的，注意的是，每组数据后面都有一个空行。

13996019

10066

The Twin Towers

Accepted

C++

0.015

2014-08-06 00:34:53

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXD 100 + 10
int dp[MAXD][MAXD];
int N1,N2,Case = 1;
int arr1[MAXD];
int arr2[MAXD];
void init(){memset(dp,0,sizeof(dp));return ;
}
void DP(){init();for(int i = 1; i <= N1 ; i++){for(int j = 1 ; j <= N2 ; j++)if(arr2[j] == arr1[i])dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1);elsedp[i][j] = max(max(dp[i][j],dp[i - 1][j]),max(dp[i][j],dp[i][j - 1]));}printf("Twin Towers #%d\n",Case++);printf("Number of Tiles : %d\n",dp[N1][N2]);printf("\n");
}
int main(){while(scanf("%d%d",&N1,&N2)){if(!N1 && !N2)break;for(int i = 1 ; i <= N1 ; i ++)scanf("%d",&arr1[i]);for(int i = 1; i <= N2 ; i++)scanf("%d",&arr2[i]);DP();}return 0;
}

这篇关于【UVA】10066-The Twin Towers（最长公共子串问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---