c语言算法优化

转个牛的解题报告！！！！

这个问题在看数据规模之前以为是个简单的DP，但是数据达到十亿，在时间和空间上太复杂了，需要优化。

解决方案1:

简单方法:期望分数30。简单的动态规划，f[i]代表一只青蛙跳到I点时可能踩到的最小石子数，所以有f[I]= min { f[k]+map[i]}(I-S≤k≤I-T)，其中map[I]代表I上是否有石子，有1，否则为0。算法复杂度为o(n ^ 2)。

解决方案2:

改进方法:期望分数100。我们会发现，桥虽然很长，但上面最多只有100块石头。不可以考虑石头是否可以用于DP。那能基于第一种方法吗？因为石头的排列非常稀疏，我们还会发现，如果两块石头相距很远，它们之间的f[i]大部分会是同一个数。能否缩短两块石头之间的距离，使之与原来相当？如果可以怎么缩小？考试的时候，王乃彦做了一个方法，把所有的数据存储在一个滚动的数组里。他的节目列表如下。我自己写了一个程序，和他不一样:我使L = stone[I]-stone[I-1](stone[I]代表按降序排列的石头的坐标)，当L能被T整除时(L%t==0)，我使K = T；当L不能被t整除时(L%t！=0)，设k = l% t .然后设k为k+t，最后判断k >是否；L，那么map[]数组中stone[i]和stone[i-1]的距离等价于L(即不变)；如果k

# include & ltstdio.h & gt

# include & ltstring.h & gt

长石[101]；

int map[100001]；

int f[100001]；

长L；

int S，T，M；

void快速排序(int l，int r)

{

int i，j；

长期温度；

I = l；

j = r；

temp = stone[I]；

while(我& ltj)

{

while(我& lt强生公司。& ampstone[j]& gt；温度)

j-；

如果(我& ltj)

{

石头[i] =石头[j]；

i++；

}

while(我& lt强生公司。& ampstone[I]& lt；温度)

i++；

如果(我& ltj)

{

石头[j] =石头[I]；

j-；

}

}

stone[I]= temp；

如果(I-1 & gt；l)快速排序(l，I-1)；

if(I+1 & lt；r)快速排序(i + 1，r)；

}

int main()

{

int i，j；

long l，k，p = 0，min

scanf("%ld%d%d%d "，& ampl & amp；s & amp；t & amp；m)；

for(I = 1；我& lt= M；i++)

scanf("%ld "，& ampstone[I])；

memset(map，0，sizeof(int)* 100001)；

memset(f，0，sizeof(int)* 100001)；

快速排序(1，M)；

stone[0]= 0；

p = 0；

for(I = 1；我& lt= M；i++)

{

l =石头[i] -石头[I-1]；

如果(l % T == 0)

k = T；

其他

k = l % T；

k = k+T；

if(l & lt；k)

k = l；

p = p+k；

map[p]= 1；

}

for(I = 1；我& lt= p+T；i++)

{

min = 1000；

for(j = I-T；j & lt= I-S；j++)

if(j & gt；= 0 & amp& ampf[j]& lt；最小)

min = f[j]；

f[I]= min+map[I]；

}

min = 1000；

for(I = p+1；我& lt= p+T；i++)

if(f[I]& lt；最小)

min = f[I]；

printf("%d\n "，min)；

返回0；

}