hdu - 3916 - Sequence Decomposition
题意：给出一个序列，其实就是一个函数，下标从1开始，把这个函数分解成几个开关函数G(x, y)的和，分法可以有多种，求各种分法中最小y-x+1的最大值。——>>这题，真贪心！
对于：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++ ,
