HDU 5773 The All-purpose Zero (DP最长上升子序列)

本文主要是介绍HDU 5773 The All-purpose Zero (DP最长上升子序列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

?? gets an sequence S with n intergers(0 < n <= 100000,0<= S[i] <= 1000000).?? has a magic so that he can change 0 to any interger(He does not need to change all 0 to the same interger).?? wants you to help him to find out the length of the longest increasing (strictly) subsequence he can get.

Input

The first line contains an interger T,denoting the number of the test cases.(T <= 10)
For each case,the first line contains an interger n,which is the length of the array s.
The next line contains n intergers separated by a single space, denote each number in S.

Output

For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the length of the longest increasing subsequence he can get.

Sample Input

  2
7
2 0 2 1 2 0 5
6
1 2 3 3 0 0

Sample Output

  Case #1: 5
Case #2: 5Hint
In the first case,you can change the second 0 to 3.So the longest increasing subsequence is 0 1 2 3 5.

Author

FZU

Source

2016 Multi-University Training Contest 4

最长上升子序列nlogn算法的稍微变形

关于最长上升子序列，表示也只写过几次（最长上升子序列），然后这次直接模板变形即可

扫到0的时候，更新各个长度的最末元素，将其变小，怎么变小，前面一个长度的最末元素+1即可

然后用sun记录0出现的次数，减少重复更新

因为0可以变成负数，所以初始化d[0] = -inf

不多说，代码很简单直接看代码

code:

#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf = 1<<29;/*Description: 最长上升子序列定义d[k]:长度为k的上升序列最末元素(终点元素)//注意d中元素是单调递增的初始化:len = 1,d[1]=a[1],然后对于a[i]:if a[i] > d[len]len++,d[len] = a[i]elsefrom d[1] to d[len]找到一个j满足 d[j-1]<a[i]<d[j]更新d[j] = a[i]
*/
const int NN = 100007;
int d[NN],a[NN];
int main()
{int n;int kas = 0;int T;scanf("%d",&T);while (T--){scanf("%d",&n);for (int i = 1;i <= n;++i){scanf("%d",a+i);}int len = 1;d[0] = -inf;d[1] = a[1];int sun = 0;for (int i = 2;i <= n;++i){if (a[i] > d[len]){d[++len] = a[i];}else if (a[i] == 0)//唯一与裸的最长上升子序列不同的地方{for (int j = len;j >= sun;--j){d[j+1] = d[j]+1;}len++;sun++;}else{int p = lower_bound(d,d+len,a[i]) - d;d[p] = a[i];}}printf("Case #%d: %d\n",++kas,len);}return 0;
}

这篇关于HDU 5773 The All-purpose Zero (DP最长上升子序列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！