题目

题目描述

有一人前来买瓜。
“哥们儿,这瓜多少钱一斤呐”
“两块钱一斤”
“What’s up，这瓜皮是金子做的,还是瓜粒子是金子做的”

智乃来到水果摊前买瓜，水果摊上贩卖着 N {N} N个不同的西瓜，第 i {i} i个西瓜的重量为 w i w_i wi​。智乃对于每个瓜都可以选择买一个整瓜或者把瓜劈开买半个瓜，半个瓜的重量为 w i 2 \frac{w_i}{2} 2wi​​。
也就是说对于每个西瓜，智乃都有三种不同的决策：

• 购买一整个重量为 w i w_i wi​的西瓜
• 把瓜劈开，购买半个重量为 w i 2 \frac{w_i}{2} 2wi​​ 的西瓜
• 不进行购买操作

为了简化题目，我们保证所有瓜的重量都是一个正偶数。

现在智乃想要知道，如果他想要购买西瓜的重量和分别为{k=1,2,3…M}k=1,2,3…M时，有多少种购买西瓜的方案，因为这些数字可能会很大，请输出方案数对 1 0 9 + 7 {10^9+7} 109+7取余数后的结果。

输入描述

第一行输入两个整数 N , M ( 0 ≤ N ≤ 1 0 3 , 1 ≤ M ≤ 1 0 3 ) {N,M(0 \leq N \leq10^3,1\leq M\leq 10^3)} N,M(0≤N≤103,1≤M≤103),分别表示西瓜的数目 N {N} N，以及查询的重量上限为 M {M} M。
若 N {N} N不为 0 {0} 0，接下来一行 N {N} N个正偶数 w i ( 2 ≤ w i ≤ 2 × 1 0 3 ) w_i (2 \leq w_i \leq2\times 10^3) wi​(2≤wi​≤2×103)表示每个西瓜的重量。

输出描述

输出一行 M {M} M个数字，分别表示购买西瓜的重量和为{k=1,2,3…M}k=1,2,3…M时，有多少种购买西瓜的方案，因为这些数字可能会很大，请输出方案数对 1 0 9 + 7 {10^9+7} 109+7取余数后的结果。

题解

#include<bits/stdc++.h>
using namespace std;
const int N = 1010,MOD = 1e9 + 7;
int f[N][N];
int V[N];
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	if(!n){
		for(int i = 0;i < m - 1;i++) printf("0 ");
		printf("0\n");
	}
	else{
		for(int i = 0;i < n;i++)
			scanf("%d",&V[i]);
		for(int i = 0;i <= n;i++) f[i][0] = 1;
		for(int i = 1;i <= n;i++)
			for(int j = 0;j <= m + 1;j++){
				f[i][j] = f[i - 1][j] % MOD;
				if(j - V[i - 1] / 2 >= 0){
					f[i][j] = (f[i][j] + f[i - 1][j - V[i - 1] / 2]) % MOD;
					if(j - V[i - 1] >= 0) f[i][j] = (f[i][j] + f[i - 1][j - V[i - 1]]) % MOD;
				}
			}
		for(int i = 1;i < m;i++) printf("%d ",f[n][i]);
		printf("%d\n",f[n][m]);
	}
	return 0;
}

动态规划入门题。
状态表示： f [ i ] [ j ] f[i][j] f[i][j]表示前 i i i个瓜，总重量为 j j j的方案数（MOD 1e9 + 7）。
状态转移方程为： f i , j = f i − 1 , j − V i − 1 + f i − 1 , j − V i − 1 2 + f i − 1 , j f_{i,j} = f_{i-1,j-V_{i-1}} + f_{i-1,j-{V_{i-1} \over 2}} + f_{i-1,j} fi,j​=fi−1,j−Vi−1​​+fi−1,j−2Vi−1​​​+fi−1,j​

题目链接

原创不易，感谢支持！