当前位置：网站首页>Zhinai buys melons (DP backpack)

Zhinai buys melons (DP backpack)

2022-07-26 01:48:00 【to cling】

2022 Niuke winter vacation algorithm basic training camp 3

Version One

The question

Insert picture description here
State transition equation ：
$d p [i] [j] = d p [i - 1] [j - w [i]] + d p [i - 1] [j - w [i] / 2]$

CODE

const int N = 2e3 + 7;
ll dp[N], a[N];
int main()
{
    
	IOS;

	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];


	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
    
		for (int j = m; j >= a[i]/ 2; j--)
		{
    
			if (j >= a[i]) 
				dp[j] = (dp[j] + dp[j - a[i]]) % mod;
			dp[j] = (dp[j] + dp[j - a[i] / 2]) % mod;
		}
	}

	for (int i = 1; i <= m; i++)
		cout << dp[i] << " ";

	return 0;
}