思路:
1.只有当当前转移过来的状态值==现有状态值 ,方案数量才会增加,增加的方案数=max(1,转移之前的方案数)
(与1取max的原因是,既然这种方案成立,方案数就不可能是1)
2.当当前转移过来的状态值>现有状态值 , 方案数=max(1,转移之前的方案数)
3.当当前转移过来的状态值>现有状态值 , 方案数不变。
注意:
1.数据范围大注意用
longlong
和取模2.要考虑到特殊情况,当一个物品都没法拿时,也是一种方案,而由于每个物品的价值都>0,所以这种情况可以用
f[v]=0
来判断
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1100,M=1e9+7;
LL f[N],s[N];
LL n,V;
int main()
{
cin>>n>>V;
while(n--)
{
LL v,w;
cin>>v>>w;
for(LL j=V;j>=v;j--)
{
if(f[j-v]+w>f[j])
{
f[j]=f[j-v]+w;
s[j]=(max(s[j-v],1LL))%M; ///注意
}
else if(f[j-v]+w==f[j]) s[j]+=(max(s[j-v],1LL))%M; ///注意
}
}
if (f[V]==0) cout<<1; //// 注意
else cout<<s[V]%M;
}