智乃买瓜 （背包dp

添加链接描述

#include
using namespace std;
const int N=1e3+9;
#define int long long
int 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<