(0/1背包问题)
记n = max(n * (n + 1) / 2) <= x + y,这样可以确定h的长度了
将1~n中的数划分为两个集合V1,V2且满足 sum(V1) <= x, sum(V2) <= y
不同数的自由组合很自然想到0/1背包解决
细节处理:n不一定恰好等于x + y,多出的部分可以全由x或y消化,或者两者一起消化,即sum(V1) + a = x, sum(V2) + b = y (其中a + b = x + y - n)
时间复杂度
O(n*sqrt(n)), 其中n = x + y
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 400010, P = 1e9 + 7;
int f[N];
int find_n(int n)
{
int l = 1, r = 1000, mid;
while (l < r)
{
mid = (l + r + 1) >> 1;
if (mid * (mid + 1) / 2 <= n) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
int x, y, k, n, t, ans = 0;
scanf("%d%d", &x, &y);
k = find_n(x + y);
f[0] = 1, n = x + y;
for (int i = 1; i <= k; i++)
{
for (int j = n; j >= i; j--)
{
f[j] = (f[j] + f[j - i]) % P;
}
}
t = n - k * (k + 1) / 2;
for (int i = x; i >= 0 && i + t >= x; i--)
{
ans = (ans + f[i]) % P;
}
printf("%d", ans);
return 0;
}