2015
04-14

# 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

.
For simplify we use G (a,b) to represent , Now the question is how to decompose the sequence to maximize the minimum length of gate function. (The length of 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 )

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 )

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

3
5
HintThe 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). 

——>>这题，真贪心！

– 右边的数），用这个方法再来将所有的a[i]减至0，结果一样——TLE；

——>>最后，考虑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;
}



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

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