12 农场周围的道路（递归+DP）

1595570448863.jpg

题目如图
这题同样是一道特别经典的状态转移的题目。

分析：
通过简单的数学计算，我们可以得出，如果n个元素，能分成两组，且两组相差为k。
那么必然其中一组为(n + k) / 2，另一组为(n - k) / 2。
其中能成功分组的条件是上面的两个式子能整除，也就是说进行地板除法后两者加起来正好等于n。
那么

1. 边界条件：if (n + k) / 2 + (n - k) / 2 ! = n : return 1；（表示不能在分组了，这个1是最后一次分组的组数）

2. 状态转移方程：
   其实状态转移方程挺简单的，仔细观察就会发现第n个元素的状态是第x1组和第x2组元素状态的和。x1, x2分别为(n + k) / 2，(n - k) / 2。
   综上： f(n) = f(x1) + f(x2);

   image.png
   （其中我们用dp数组保存下节点状态，因为存在大量的重复节点运算）
   这里我们发现题目数据最大是1e9，开不了这么大内存的数组，我们可以使用STL另一个方便的数据结构帮助我们：map，这是一种二叉树结构的高效查找的数据结构。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;

map<int, int> dp;

int f(int n, int k) {
    int x1 = (n + k) / 2, x2 = (n - k) / 2;
    // 不能够再分了
    if (x1 + x2 != n || n <= k) {
        return 1;
    }
    if (dp[n]) return dp[n];
    else return dp[n] = f(x1, k) + f(x2, k);
}

void solve(int n, int k) {
    printf("%d", f(n, k));
}

int main(int argc, char const *argv[])
{
    int n, k;
    scanf("%d%d", &n, &k);
    solve(n, k);

    return 0;
}

运行结果： image.png image.png