题目描述
blablabla
样例
blablabla
算法1
(01背包) $O(min(x,y)*sqrt(x+y))$
先确定h的最大值,然后问题转化为对体积为1,2……h的物品做01背包,其中背包体积为x
但还需要考虑一点,这里其实是两个背包,体积分别为x,y。在保证x的体积不超的前提下,还需要保证y的体积也不超。
设所有物品总体积为sum=h*(h+1)/2,则背包体积为x的背包装的物品总体积范围应为max(0,sum-y)~x(当V(x)< sum-y时V(y)> y,不符要求;sum也有可能<=y,但凑出体积的最小值只能为0,不能为负数,所以左边界要和0取max)
状态定义:f[i]表示从体积为1~h中的物品中选(每种物品只有一个),凑成总体积为i的方案总数
则根据上面的分析,ans=sum(f[max(0,sum-y)~x])
最后不要忘记取模(状态转移过程和计算结果过程均要取)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int x,y;
const int mod=1e9+7;
ll f[400010];
int h=0;
int main()
{
cin>>x>>y;
while(h*(h+1)/2<=x+y) h++;
h--;
//cout<<h<<endl;
f[0]=1;
for(int i=1;i<=h;i++)
{
for(int j=x;j>=i;j--)
{
f[j]=(f[j]+f[j-i])%mod;
}
}
ll ans=0;
int sum=h*(h+1)/2;
//cout<<sum<<endl;
for(int i=x;i>=max(0,sum-y);i--) ans=(ans+f[i])%mod;
cout<<ans<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla