首页 > ACM题库 > HDU-杭电 > HDU 4604-Deque-分治-[解题报告]HOJ
2015
09-17

HDU 4604-Deque-分治-[解题报告]HOJ

Deque

问题描述 :

Today, the teacher gave Alice extra homework for the girl weren’t attentive in his class. It’s hard, and Alice is going to turn to you for help.
The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or rear end. Alice was asked to take out the elements from the sequence in order(from A_1 to A_N), and decide to push it to the front or rear of the deque, or drop it directly. At any moment, Alice is allowed to pop the elements on the both ends of the deque. The only limit is, that the elements in the deque should be non-decreasing.
Alice’s task is to find a way to push as many elements as possible into the deque. You, the greatest programmer, are required to reclaim the little girl from despair.

输入:

The first line is an integer T(1≤T≤10) indicating the number of test cases.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.

输出:

The first line is an integer T(1≤T≤10) indicating the number of test cases.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.

样例输入:

3
7
1 2 3 4 5 6 7
5
4 3 2 1 5
5
5 4 1 2 3

样例输出:

7
5
3

题目大意就是给一个deque

然后有n个数,依次进行操作,每种操作,你可以把这个数放在deque首部,也可以放在尾部,也可以扔掉不管,但是要保证deque中的数是非递减的。最要求deque中最长能是多少

思路是这样的:对于这个序列,最重要的应该是第一个进去的数是什么,然后以该数为开头的最长不升子序列和以该数为开头的最长不降子序列则可以凑成一个最长的序列,当然这两个序列中可能都出现了该数,也就是发生了重复,所以就要减掉重复的部分,即两个子序列中有该数个数较少的序列中这个数应当被减掉。

那么为什么能减掉呢? 其实先手写几个样例就知道,两个序列中如果都有若干该数,必有一个序列中拥有的该数是另外一个序列中拥有的该数的子集

也可以证明一下:

假设以某个数开头的两个序列分别为a1,a2,a3,…..,an, 以及 b1,b2,b3,…..,bm

首先我们知道a1=b1,这是显然的。

然后假设a数组中前i项是与a相等的,b中前j项是与b1相等的。 

那么必有a(i+1) != b(j+1)

假设二者在数组中的位置分为pos1, pos2

若pos1 < pos2

我们知道b数组中1到i的元素都是相同的值,也就是pos2之前所有的元素是该值的都加入了b数组中,那么显然pos1之前的该值显然也都在

也就是说a数组中包含的该元素是b数组的子集

pos1 > pos2时一样可证

然后由于数据量大,所以要用到二分求最长上升子序列的方法

顺便使用了stl中的equal_range函数,意思就是返回一个区间[it1,it2) 然后区间内的数都是要查找的那个数。  这就使得我们计算序列中有多少个某个数时提供了方便。

开两种数组,一种是以当前某数为开头的不降 /不增序列的最大长度,一种是某数在这不降/不升 序列中出现的次数。

然后倒着求,这样到了某数时,就知道以它开头的不降/不增序列的最大长度。

最后枚举一遍进deque的第一个数即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define MAXM 111111
#define MAXN 111111
#define INF 1000000007
#define eps 1e-8
using namespace std;
typedef vector<int>::iterator Viter;
int n;
vector<int>g;
int a[MAXN];
int dp1[MAXN], dp2[MAXN], num1[MAXN], num2[MAXN];
void gao(int dp[], int num[])
{
    g.clear();
    Viter it;
    for(int i = n – 1; i >= 0; i–)
    {
        int sz = g.size();
        if(!sz || a[i] >= g[sz - 1])
        {
            g.push_back(a[i]);
            dp[i] = sz + 1;
        }
        else
        {
            it = upper_bound(g.begin(), g.end(), a[i]);
            dp[i] = it – g.begin() + 1;
            *it = a[i];
        }
        pair<Viter, Viter>bounds = equal_range(g.begin(), g.end(), a[i]);
        num[i] = bounds.second – bounds.first;
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T–)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        gao(dp1, num1);
        for(int i = 0; i < n; i++) a[i] = -a[i];
        gao(dp2, num2);
        int ans = 0;
        for(int i = 0; i < n; i++)
            ans = max(ans, dp1[i] + dp2[i] – min(num1[i], num2[i]));
        printf("%d\n", ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/9721909