hdu - 3916 - Sequence Decomposition

 

——>>这题，真贪心！

对于：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就好，有点类似线段树的下传机制。

[cpp]  

#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])      //找到右界  

                {  www.zzzyk.com

                    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;  

}  

 

补充：软件开发 , C++ ,