AcWing 4421. 信号(记忆化搜索)
原题链接
困难
记忆化搜索
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int fx = 1e5 + 7;
int n, r;
int g[N];
int mp[N][N];
int dfs(const int& x, const int& y)
{
if (mp[x][y] != -1) return mp[x][y];
if (y >= n) return 0;
if (x == n) return fx;
if (g[x] == 0) return dfs(x + 1, y);
if (y < x - r + 1) return fx;
int res = min(dfs(x + 1, y), 1 + dfs(x + 1, max(x + r, y)));
mp[x][y] = res;
return res;
}
int main()
{
cin >> n >> r;
for (int i = 0; i < n; ++ i) cin >> g[i];
memset(mp, -1, sizeof mp);
int ans = dfs(0, 0);
cout << (ans > n ? -1 : ans);
return 0;
}
htt yyds