【带限制的完全背包】Educational Codeforces Round 133 (Rated for Div. 2) D. Chip Move
2023-11-04
题意: 给定
n
n
n 和
k
k
k,初始步长为
k
k
k ,每次可以走
k
k
k 的倍数次步,下一次走
(
k
+
1
)
(k+1)
(k+1)的倍数次步,以此类推,问从
0
0
0 开始到达
[
1
,
n
]
[1,n]
[1,n] 每个点的方案数。
题解: 当每次只走一倍的步数时,
(
s
t
e
p
+
k
)
×
(
s
t
e
p
−
k
+
1
)
2
≤
n
\frac{(step+k)\times (step-k+1)}{2}\leq n
2(step+k)×(step−k+1)≤n,所以最多只会走
O
(
n
)
O(\sqrt{n})
O(n)次。
问题转换为带限制的完全背包问题,走第
i
i
i 次前,必须已经走了
1
1
1 到
i
−
1
i-1
i−1次
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示走了
i
i
i次,第
i
i
i 次走完后到达点
j
j
j 的方案数 第
i
i
i 次走的步数为
(
k
+
i
−
1
)
(k+i-1)
(k+i−1) 的倍数
不带限制的完全背包的模板为:
for(int i =1; i <= n;++i) f[i]=0;
f[0]=1;for(int step = k;(start =(step + k)*(step - k +1)/2)<= n;++step)for(int j =0; j <= n;++j)if(j >= step) f[i][j]+= f[i -1][j - step];
但是本题的限制为:走第
i
i
i 次前,必须已经走了
1
1
1 到
i
−
1
i-1
i−1次 每次需要强制走一下第
i
−
1
i-1
i−1 次,如下: