智乃买瓜（背包dp

添加链接描述

#includeusing namespace std;const int N=1e3+9;#define int long longint dp[N][N],mod=1e9+7;signed main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ int w; cin>>w; for(int j=m;j>=0;j--){ if(j>=w){ dp[i][j]=(dp[i][j]+dp[i-1][j-w]+1)%mod; } if(j>=w/2){ dp[i][j]=(dp[i][j]+dp[i-1][j-w/2]+1)%mod; } dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;//不买 } } int sum=0; for(int i=1;i<=m;i++){ sum=(sum+dp[n][i-1])%mod; dp[n][i]=(dp[n][i]-sum+mod)%mod; cout<