题意：给出一个序列，其实就是一个函数，下标从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 3for(; 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;
}