P5940 [POI1997] 跳 题解

· · 题解

前言

挺有意思的题，记录一下。

正文

分析题目

简化一下题意，有一个无限长的的数组，从负无穷到正无穷，然后初始这个数组上一些点有一些数，现在可以使用两种操作让这个数组任意两个相邻的数的和不超过一，首选选择一个下标 p：

  1. 让 a_p 加一，a_{p-1},a_{p-2} 减一。

  2. 让 a_p 减一，a_{p-1},a_{p-2} 加一。

首先这两个操作是互逆的。然后这个操作会给人一种感觉，就是 p-1,p-2 位置上的数各取一，和一个 p 位置取一是等价的。所以可以花费 p-1,p-2 位置各减去一作为代价，让 p 位置加上一，另一个操作同理。

那就给每个位置钦定一个权值 w_p 可以满足这样的条件，肯定有 w_p=w_{p-1}+w_{p-2}，即斐波那契数列。这样每次操作后数组的带权和不变，我们令这个值是 s，那么结束状态就是把 s 拆分成不同且不相邻的一些斐波那契数之和，所以把问题转化为求一个数的斐波那契拆解（我也不知道这个叫什么）。

求解方法很简单，每次减去小于等于这个数的最大斐波那契数即可。为什么这样是对的呢，用归纳法证明，首先 s 是一或者二可以直接拆解，那么设当前已知分解方法的最大的数是 n，现在来分解 n+1，找到的小于等于 n+1 的最大斐波那契数是 f，那么 n+1-f\leq n 所以一定能拆解下去。那么可不可能分解出来有相邻的数呢？不可能，假设分解出 fib_{i-1} 和 fib_i，再找最大的斐波那契数的时候就会找 fib_{i+1} 了，而不是这两个。

代码实现

由于需要高精，建议使用 python 实现，并且钦定权值要从小一点的地方开始钦定，这里建议是 -100。

B=100
n=int(input())

pos=[0]*100010
val=[0]*100010
fib=[0]*200010
fib[0]=fib[1]=1
res=[]

sumFib=0
cnt=0

minp=0x3f3f3f3f
maxp=0

for i in range(0,n):
    [pos[i],val[i]]=map(int,input().split())
    maxp=max(pos[i],maxp)
    minp=max(pos[i],minp)

cnt=maxp+B
for i in range(2,cnt+1):
    fib[i]=fib[i-1]+fib[i-2]

for i in range(0,n):
    sumFib+=fib[pos[i]+B]*val[i]

while fib[cnt]<sumFib:
    fib[cnt+1]=fib[cnt]+fib[cnt-1]
    cnt+=1

while sumFib>0:
    while fib[cnt]>sumFib:
        cnt-=1
    res.append(cnt-B)
    sumFib-=fib[cnt]

res.reverse()

print(*res)