1595570448863.jpg
题目如图
这题同样是一道特别经典的状态转移的题目。
分析：
通过简单的数学计算，我们可以得出，如果n个元素，能分成两组，且两组相差为k。
那么必然其中一组为(n + k) / 2，另一组为(n - k) / 2。
其中能成功分组的条件是上面的两个式子能整除，也就是说进行地板除法后两者加起来正好等于n。
那么
边界条件：if (n + k) / 2 + (n - k) / 2 ! = n : return 1；（表示不能在分组了，这个1是最后一次分组的组数）
-
状态转移方程：
其实状态转移方程挺简单的，仔细观察就会发现第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
