题目
题目描述
有一人前来买瓜。
“哥们儿,这瓜多少钱一斤呐”
“两块钱一斤”
“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
原创不易，感谢支持！