HDU4512完美队形I && HDU1423 Greatest Common Increasing Subsequence (LCIS)

时间:2022-06-04 07:10:57

填坑的时候又到啦,校赛因为不会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)的更多相关文章

  1. HDU 1423 Greatest Common Increasing Subsequence LCIS

    题目链接: 题目 Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: ...

  2. HDU1423 Greatest Common Increasing Subsequence

    题意 如标题. \(|s1|,|s2| \leq 500\) 分析 既然是dp问题的组合,那么考虑dp. 定义状态f(i,j)表示对第一个序列s1的前i个和第二个序列s2的前j个元素求最长上升公共子序 ...

  3. HDU1423:Greatest Common Increasing Subsequence&lpar;LICS&rpar;

    Problem Description This is a problem from ZOJ 2432.To make it easyer,you just need output the lengt ...

  4. Greatest Common Increasing Subsequence hdu1423

    Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536 ...

  5. POJ 2127 Greatest Common Increasing Subsequence -- 动态规划

    题目地址:http://poj.org/problem?id=2127 Description You are given two sequences of integer numbers. Writ ...

  6. HDOJ 1423 Greatest Common Increasing Subsequence -- 动态规划

    题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1423 Problem Description This is a problem from ZOJ 2 ...

  7. ZOJ 2432 Greatest Common Increasing Subsequence(最长公共上升子序列&plus;路径打印)

    Greatest Common Increasing Subsequence 题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problem ...

  8. HDU 1423 Greatest Common Increasing Subsequence&lpar;最长公共上升LCIS&rpar;

    HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS) http://acm.hdu.edu.cn/showproblem.php?pi ...

  9. POJ 2127 Greatest Common Increasing Subsequence

    You are given two sequences of integer numbers. Write a program to determine their common increasing ...

随机推荐

  1. Python—redis

    一.redis redis是一个key-value存储系统.和Memcached类似,它支持存储的value类型相对更多,包括string(字符串).list(链表).set(集合).zset(sor ...

  2. Spring Dynamic Modules - DMserver

    spring dm server 官网:http://static.springsource.com/projects/dm-server/1.0.x/programmer-guide/htmlsin ...

  3. 如何使用Visual Studio 2013 创建Azure云应用

    创建 Azure 云服务 Azure 云服务包括执行应用程序所需操作的角色.当你将云服务发布到 Azure 时,每个角色将在云中的虚拟机上运行.有关如何开发 Azure 云服务的详细信息. 创建 Az ...

  4. HDU2084 数塔 &lpar;DP入门题&rpar;

    数塔 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...

  5. zen-coding for notepad&plus;&plus;,前端最佳手写代码编辑器

    zen-Coding是一款快速编写HTML,CSS(或其他格式化语言)代码的编辑器插件,这个插件可以用缩写方式完成大量重复的编码工作,是web前端从业者的利器. zen-Coding插件支持多种编辑器 ...

  6. SVN与eclipse整合和利用、SVN与Apache综合

    SVN与eclipse综合 下载SVN插入(http://subclipse.tigris.org) http://subclipse.tigris.org/servlets/ProjectDocum ...

  7. QT自动补全设置

    在工具 -> 选项 -> 环境 -> 键盘 中,找到TextEditor -> CompleteThis,修改后面的快捷键就好了 我将它修改为Alt + /

  8. 转&colon;运行page页面时的事件执行顺序及页面的回发与否深度了解

    using System; using System.Data; using System.Configuration; using System.Web; using System.Web.Secu ...

  9. SpringCloud的注解:EnableEurekaClient vs EnableDiscoveryClient

    What's the difference between EnableEurekaClient and EnableDiscoveryClient? In some applications, I ...

  10. Ubuntu下配置使用mysql

    很多生产环境都使用linux系统,相比于window系统,界面真的做的不够人性化,但是简洁高效也是linux的优点吧.在linux上使用mysql又是不一样的风景吧.