题目翻译
一只青蛙生活在 Ox 轴上,需要到达位于 n 点的家。 她从点 1 开始。青蛙可以在不超过 d 的距离处向右跳。 所以,她从点 x 跳跃后,可以到达点 x + a,其中 a 是从 1 到 d 的整数。
对于从 1 到 n 的每个点,都知道其中是否有一朵百合花。 青蛙只能用百合花点跳。 保证1点和n点都有百合花。
确定青蛙需要到达家的最小跳跃次数,即从点 1 到点 n 处。考虑最初青蛙在点 1。如果青蛙无法到达家,则打印 -1。
题目分析
搜索每种情况+贪心
代码
#includeusing namespace std; char a[10001]; int res = 0,flag=1; int main() { int n, m, k; cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; if (a[0] == '0' || a[n-1] == '0') { cout << -1; return 0; } for (int i = 0; i < n-1;) { k = i; for (int j = m; j > 0; j--)//每一步都先往最远的地方 { if (a[i + j] == '1') { k = i + j; res++; break; } } if (k == i) { cout << -1; return 0; } i = k; } cout << res; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)