首页 > ACM题库 > HDU-杭电 > HDU 3916-Sequence Decomposition-贪心-[解题报告]HOJ
2015
04-14

HDU 3916-Sequence Decomposition-贪心-[解题报告]HOJ

Sequence Decomposition

问题描述 :

A sequence can be decomposed into the sum of unit impulses, but we can still decompose the sequence into the sum of gate function which defined as
  
Game
.
  For simplify we use G (a,b) to represent Game, Now the question is how to decompose the sequence to maximize the minimum length of gate function. (The length of Game is b �C a + 1). For simplification, you just need to get the minimum length.

输入:

The first integer T is the number of test cases
Each case starts with a number N followed by N integers a[i]  
(0<= T <= 10)
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure Game)

输出:

The first integer T is the number of test cases
Each case starts with a number N followed by N integers a[i]  
(0<= T <= 10)
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure Game)

样例输入:

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

样例输出:

3
5
Hint
The first case can be decomposed to G(1,5)+G(1,6)+G(2,5)+G(3,3), the minimum length is 1 and it can also be decomposed to G(1,3)+G(1,5)+G(2,6)+G(3,5), the minimum length is 3, so answer is 3. The second case can be decomposed to 2*G (1, 5).

题意:给出一个序列,其实就是一个函数,下标从1开始,把这个函数分解成几个开关函数G(x, y)的和,分法可以有多种,求各种分法中最小y-x+1的最大值。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3916

——>>这题,真贪心!

对于:2 2 2 

显然,分解成3个G(1, 3)时最小长度y-x+1 = 3;如果不是,那么其最小长度一定比3小——可得——两数相等的时候,应把它们归到一个G中。

对于:2 4 2

如果第一步将2, 4归到一个G,而不要后面的2时,将得到2G(1, 2) + 2G(2, 3),此时最小长度为2;如果开始时三个数归到一个G,那么得到2G(1, 3) + 2G(2, 2),此时最小长度为1——可得——增大时归到一个G,减小时不归到一个G,才能使最小长度最大。

开始时我将输入的数据存入数组a,对a一次次的a[i]–,一直到所有的a[i] == 0,结果不用说——TLE;

接着,看到对于2 3 3 7 4 1,a[1]到a[4]可以直接-2(左边第一个最小数2),对于4 4 4  7 4 1,a[1]到a[4]可以直接-3(右边最大一个
– 右边的数),用这个方法再来将所有的a[i]减至0,结果一样——TLE;

可以想到,不能这样直接将所有的a[i]减至0!!!

——>>最后,考虑G(L, R),用m[R]表示a[L]到a[R]要减的量,扫描一次a,维护m与一个左边最小数要减的temp就好,有点类似线段树的下传机制。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 10000 + 10;

int main()
{
    int T, N, i;
    long long a[maxn], m[maxn];     //a为输入数组,m[R]表示a[L]到a[R]要减的量
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &N);
        for(i = 1; i <= N; i++) scanf("%I64d", &a[i]);
        a[N+1] = 0;     //最后加个0,好处理
        int L = 1, R = 1, temp = 0, minn = 2147483647;      //G(L, R),temp为根据后面确定的a[L]要减的量,minn为结果
        memset(m, 0, sizeof(m));
        while(L <= N)
        {
            for(; L <= N; L++)
                if(!(a[L]-temp)) temp -= m[L];      //更新
                else break;     //找到第一个不是0的a[L]
            if(L > N) continue;     //完成
            if(R < L) R = L;        //有可能的,如2 2 2 3 3
            for(; R <= N; R++)
                if(a[R+1] < a[R]-m[R])      //找到右界
                {
                    minn = min(minn, R-L+1);        //更新
                    long long dis = a[R] - m[R] - a[R+1];       //dis个G(L, R)
                    dis = min(dis, a[L]-temp);
                    m[R] += dis;        //累加增量
                    temp += dis;        //更新
                    break;
                }
        }
        printf("%d\n", minn);
    }
    return 0;
}

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

参考:http://blog.csdn.net/scnu_jiechao/article/details/8584981


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮