填坑的时候又到啦,校赛因为不会LCIS所以吃了大亏,这里要补起来。LCIS就是在两个串里找最长上升子序列,相关的博客有很多,这里自己就不写那么多了。
http://www.cnblogs.com/jackge/archive/2013/05/16/3081793.html
http://www.cnblogs.com/gj-Acit/p/3236384.html
上面两个博客对于O(n^2)的做法讲解的比较详细,大家可以参考一下。
贴两记代码
HDU1423
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std; #define maxn 550
int a[maxn];
int b[maxn];
int n1, n2;;
int dp[maxn][maxn]; int main()
{
int T; cin >> T;
while (T--){
cin >> n1;
for (int i = 1; i <= n1; i++) scanf("%d", a + i);
cin >> n2;
for (int i = 1; i <= n2; i++) scanf("%d", b + i);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n1; i++){
int tmp = 0;
for (int j = 1; j <= n2; j++){
dp[i][j] = dp[i - 1][j];
if (a[i] > b[j] && dp[i - 1][j] > tmp) tmp = dp[i - 1][j];
if (a[i] == b[j]) dp[i][j] = tmp + 1;
}
}
int ans = 0;
for (int i = 1; i <= n1; i++){
ans = max(ans, dp[n1][i]);
}
printf("%d\n", ans);
if (T) puts("");
}
return 0;
}
HDU4512
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std; #define maxn 550 int a[maxn];
int b[maxn];
int n;
int dp[maxn][maxn]; int main()
{
int T; cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++){
scanf("%d", a + i);
b[n + 1 - i] = a[i];
}
int ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++){
int tmp = 0;
for (int j = 1; j <= n+1-i; j++){
dp[i][j] = dp[i - 1][j];
if (a[i] > b[j] && dp[i - 1][j] > tmp) tmp = dp[i - 1][j];
if (a[i] == b[j]){
dp[i][j] = max(dp[i][j],tmp + 1);
}
if (i < n + 1 - j) ans = max(ans, dp[i][j] * 2);
else ans = max(ans, dp[i][j] * 2 - 1);
}
}
printf("%d\n", ans);
}
return 0;
}
HDU4512完美队形I && HDU1423 Greatest Common Increasing Subsequence (LCIS)的更多相关文章
-
HDU 1423 Greatest Common Increasing Subsequence LCIS
题目链接: 题目 Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: ...
-
HDU1423 Greatest Common Increasing Subsequence
题意 如标题. \(|s1|,|s2| \leq 500\) 分析 既然是dp问题的组合,那么考虑dp. 定义状态f(i,j)表示对第一个序列s1的前i个和第二个序列s2的前j个元素求最长上升公共子序 ...
-
HDU1423:Greatest Common Increasing Subsequence(LICS)
Problem Description This is a problem from ZOJ 2432.To make it easyer,you just need output the lengt ...
-
Greatest Common Increasing Subsequence hdu1423
Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536 ...
-
POJ 2127 Greatest Common Increasing Subsequence -- 动态规划
题目地址:http://poj.org/problem?id=2127 Description You are given two sequences of integer numbers. Writ ...
-
HDOJ 1423 Greatest Common Increasing Subsequence -- 动态规划
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1423 Problem Description This is a problem from ZOJ 2 ...
-
ZOJ 2432 Greatest Common Increasing Subsequence(最长公共上升子序列+路径打印)
Greatest Common Increasing Subsequence 题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problem ...
-
HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS)
HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS) http://acm.hdu.edu.cn/showproblem.php?pi ...
-
POJ 2127 Greatest Common Increasing Subsequence
You are given two sequences of integer numbers. Write a program to determine their common increasing ...
随机推荐
-
Python—redis
一.redis redis是一个key-value存储系统.和Memcached类似,它支持存储的value类型相对更多,包括string(字符串).list(链表).set(集合).zset(sor ...
-
Spring Dynamic Modules - DMserver
spring dm server 官网:http://static.springsource.com/projects/dm-server/1.0.x/programmer-guide/htmlsin ...
-
如何使用Visual Studio 2013 创建Azure云应用
创建 Azure 云服务 Azure 云服务包括执行应用程序所需操作的角色.当你将云服务发布到 Azure 时,每个角色将在云中的虚拟机上运行.有关如何开发 Azure 云服务的详细信息. 创建 Az ...
-
HDU2084 数塔 (DP入门题)
数塔 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...
-
zen-coding for notepad++,前端最佳手写代码编辑器
zen-Coding是一款快速编写HTML,CSS(或其他格式化语言)代码的编辑器插件,这个插件可以用缩写方式完成大量重复的编码工作,是web前端从业者的利器. zen-Coding插件支持多种编辑器 ...
-
SVN与eclipse整合和利用、SVN与Apache综合
SVN与eclipse综合 下载SVN插入(http://subclipse.tigris.org) http://subclipse.tigris.org/servlets/ProjectDocum ...
-
QT自动补全设置
在工具 -> 选项 -> 环境 -> 键盘 中,找到TextEditor -> CompleteThis,修改后面的快捷键就好了 我将它修改为Alt + /
-
转:运行page页面时的事件执行顺序及页面的回发与否深度了解
using System; using System.Data; using System.Configuration; using System.Web; using System.Web.Secu ...
-
SpringCloud的注解:EnableEurekaClient vs EnableDiscoveryClient
What's the difference between EnableEurekaClient and EnableDiscoveryClient? In some applications, I ...
-
Ubuntu下配置使用mysql
很多生产环境都使用linux系统,相比于window系统,界面真的做的不够人性化,但是简洁高效也是linux的优点吧.在linux上使用mysql又是不一样的风景吧.