题意:求最长公告子序列。
裸体,压缩了空间做的,O(n^2)做法,有空研究下nlogn做法。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: uva10066.cpp
* Create Date: 2013-09-21 09:31:21
* Descripton: dp, LCS
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 101;
int n, m, dp[2][MAXN], a[MAXN], b[MAXN];
int main() {
int cas = 0, k = 1;
while (scanf("%d%d", &n, &m) && (n || m)) {
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int j = 1; j <= m; j++) {
scanf("%d", &b[j]);
dp[0][j] = dp[1][j] = 0;
}
for (int i = 1; i <= n; i++) {
k = !k;
for (int j = 1; j <= m; j++)
if (a[i] == b[j])
dp[k][j] = max(dp[!k][j - 1] + 1, dp[k][j]);
else
dp[k][j] = max(dp[k][j - 1], dp[!k][j]);
}
printf("Twin Towers #%d\n", ++cas);
printf("Number of Tiles : %d\n\n", dp[k][m]);
}
return 0;
}
分享到:
相关推荐
双塔防御
该项目收集了许多编程语言中的经典“河内塔”问题,包括鲜为人知和/或深奥的语言。
该程序是经典的Hanoi塔问题的Java语言版.河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的
matlab开发-TowersofHanoi。一个Matlab图形用户界面为河内流行的双塔益智游戏提供手动或自动解决方案。
There are two fundamental types of HVAC systems designed to satisfy buildingcooling requirements: direct expansion (DX) systems in which there is directheat exchange between the building air and the ...
国际基站数据库
towers_perrin2.doc
Towers of Hanoi Hanoi 用pb编程 可播放声音、单步执行
Cities are most interesting when they combine the new with the old, and the traditional with the avant-garde. New York juxtaposes high rises with church spires, crammed spaces with green vistas, ...
towersofhanoi-源码.rar
optiplex-3000-towers-spec-sheet
Based on wind speed and direction records from wind measurement towers at six onshore sites with different geographical climate conditions in China, statistical assessment of wind characteristics and ...
(3)the pylons (or towers) supporting the cable system; (4)the anchor blocks (or anchor piers) supporting the cable system vertically and horizontally, or only vertically, at the extreme ends.
Danwei Li_ESCP Europe MiM_Willis Towers Watson_Investment Analyst.pdf
反光塔 翻译反射塔的软件考古学 3-Lisp 布朗(,) 金发(,) 黑色(,)
Baking Cupcake Towers Chapter 3. Communicating with the Player – the User Interface Chapter 4. No Longer Alone – Sweet-Toothed Pandas Strike Chapter 5. The Secret Ingredient Is a Dash of Physics ...
Baking Cupcake Towers Chapter 3. Communicating with the Player – the User Interface Chapter 4. No Longer Alone – Sweet-Toothed Pandas Strike Chapter 5. The Secret Ingredient Is a Dash of Physics ...
You can use towers to besiege creeps in the game ,don't let the creeps hurt princess. There are more than 40 creeps will take turn to attack the princess and they will became more and more powerful....
Practice for GUI course