频道栏目
首页 > 考试 > 其他 > 正文
HDU - 5773 The All-purpose Zero(思维+LIS)
2017-09-04 10:03:25         来源:K键盘里的青春K  
收藏   我要投稿

HDU - 5773 The All-purpose Zero(思维+LIS)。

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: 5

Hint

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

题意:

可以将0替换成任意interger(包括负数),在此基础上求最长递增子序列。

思路:

对于这个题目,我只想%一下出题大佬!

首先要知道,把所有的0都用上一定不会使答案变得更差.

这个题目确实有助于你理解nlogn复杂度求LIS的算法,dp[i]数组保存的就是当前LIS长度为i的末尾最小的一个数,

那么举个例子 1 2 3 0 0 4.

我们抛开别的长度不说了吧,就只说说长度为3。

长度为3的最后一个最小的是3,那么新增加一个0的话,长度为4结尾的最小就为4了,也就是dp【3】+1.

长度为5的,就是dp【4】+1,因为这里是严格递增,那么再来一个4的话,已经无法加入是答案变得更好了.

那么我们发现有一个0的话就是使最优的那个+1,从反面来考虑就相当于当前0后面所有非0的数都-1,这样所有0后面的都减1得到的LIS没有影响.

所以这个题目就是把所有的0拿出来,对于每一个非0的就减去前面所有0的个数,对所有非0的数求一个LIS,然后+0的个数即可.

PS:可能举的例子不合适,需要自己好好理解了

总结:要学会思维转化, 倒着想的思想很重要, 比赛里做这题的时候, 我曾经贪心过一下, 是不是把0变成前面数+1是不是一定是最优的, 因为我觉得 0 一定可以使答案更优,但是不知道到底变成哪个,总有后效性,这题如果倒着想的话,好想太多太多了。0一定可以使答案最优,我有0就用,就当作最优解中的一个,这样把每个数,都-去前面0的个数,如果还能跟前面连起来, 说明中间的0可以插入形成一个上升子序列,这样每个数都减去前面0的个数,就相当于“抠出”一块空的来,让0来插进来,因为0一定可以让答案最优,一定可以作为答案的一部分,然而正着想并不知道让0变成什么,这种转化思维比较好。

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], pre[maxn], num[maxn], b[maxn];
int main()
{
    int t, n, ca = 1;
    scanf("%d", &t);
    while(t--)
    {
        memset(pre, 0, sizeof(pre));
        memset(b, 0, sizeof(b));
        memset(num, 0, sizeof(num));
        scanf("%d", &n);
        int cnt = 0, tot = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            if(a[i] == 0)
                pre[i] = pre[i-1] + 1, cnt++;
            else
                pre[i] = pre[i-1];
        }
        for(int i = 1; i <= n; i++)
        {
            if(a[i] != 0)
                num[tot++] = a[i] - pre[i];
        }
        int len = 1, l , mid, r;
        if(tot == 0) len = 0;
        b[1] = num[0];
        for(int i = 1; i < tot; i++)
        {
            l = 1, r = len;
            while(l <= r)
            {
                mid = (l+r)/2;
                if(b[mid] < num[i]) l = mid+1;
                else r = mid - 1;
            }
            b[l] = num[i];
            if(l > len) len++;
        }
        printf("Case #%d: %d\n", ca++, len+cnt);
    }
    return 0;
}

 


点击复制链接 与好友分享!回本站首页
上一篇:hdu4821 String (字符串hash + map)
下一篇:Shape Number HDU - 4162(最小表示法)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站