算法
(单调队列优化dp、dp復元) $O(N)$
记 dp[i]
表示第 $i$ 个格子跳到第 $N$ 个格子所需的最少步数。
转移方程:
$ dp[i] = \min\limits_{1 \leqslant k \leqslant M} dp[i + k] + 1 $
转移数为 $O(N)$,所以总的时间复杂度就是 $O(NM)$,显然超时
下面考虑优化:
注意到这个DP序列单调递减,所以我们可以用单调队列来维护 $\min\limits_{1 \leqslant k \leqslant M} dp[i + k]$,这样转移数就降到了 $O(1)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
using std::string;
int main() {
int n, m;
string s;
cin >> n >> m >> s;
const int INF = 1<<30;
vector<int> dp(n+1, INF);
dp[n] = 0;
queue<int> q;
q.push(0);
for (int i = n-1; i >= 0; --i) {
while (1) {
if (q.size() == 0) {
puts("-1");
return 0;
}
if (q.front() != INF and q.size() <= m) break;
q.pop();
}
if (s[i] == '0') dp[i] = q.front() + 1;
q.push(dp[i]);
}
vector<int> ans;
int x = 0;
int rest = dp[0];
while (x < n) {
--rest;
int i = 1;
while (dp[x+i] != rest) ++i;
ans.push_back(i);
x += i;
}
for (int x : ans) cout << x << ' ';
return 0;
}