题目描述

难度分:$1000$

输入$n(1 \leq n \leq 10^4)$和$m(2 \leq m \leq 10)$。

从$s=0$开始，每次操作可以把$s$增加$1$或者增加$2$。

目标是让$s=n$，且操作次数必须是$m$的倍数。

输出最少操作次数。如果无法做到，输出$-1$。

输入样例$1$

10 2

输出样例$1$

6

输入样例$2$

3 5

输出样例$2$

-1

算法

记忆化搜索

比较模板的一道题，很容易想到思路。

状态定义

$dp[cur][op]$表示当前$s=cur$，且已经进行的操作次数模$m$的值为$op$的情况下，后续要达成$s=n$最少需要的操作次数。在这个定义下，答案就应该是$dp[0][0]$。

状态转移

分为以下三种情况转移：

1. $cur \gt n$时，由于$s$只能增大，这时候肯定无解，答案为正无穷。
2. $cur=n$时，如果$op \neq 0$，不满足操作次数是$m$的倍数，也是无解。
3. $cur \lt n$时，有两种策略，对$s$加$1$或者加$2$。状态转移方程为$dp[cur][op]=1+min(dp[cur+1][(op+1) \% m],dp[cur+2][(op+1) \% m])$。

复杂度分析

时间复杂度

状态数量为$O(nm)$，单次转移的时间复杂度为$O(1)$，所以整个算法的时间复杂度为$O(nm)$。

空间复杂度

空间消耗的瓶颈就在于记忆化搜索时的状态矩阵$dp$，空间复杂度为$O(nm)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 11;
const int INF = 0x3f3f3f3f;
int n, m;

int dp[N][M]; // 记忆化数组

int dfs(int cur, int op) {
    if(cur > n) {
        return INF;
    }
    if(cur == n) {
        return op == 0 ? 0 : INF;
    }
    if(dp[cur][op] != -1) {
        return dp[cur][op];
    }
    dp[cur][op] = 1 + min(dfs(cur + 1, (op + 1) % m), dfs(cur + 2, (op + 1) % m));
    return dp[cur][op];
}

int main() {
    scanf("%d%d", &n, &m);
    memset(dp, -1, sizeof(dp));
    int ans = dfs(0, 0);
    if (ans >= INF) {
        ans = -1;
    }
    printf("%d\n", ans);
    return 0;
}