智乃买瓜

题意

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

  1. 购买一整个重量为 $w_{i}$ 的西瓜
  2. 把瓜憵开, 购买半个重量为 $\frac{w_{i}}{2}$ 的西瓜
  3. 不进行购买操作
    为了简化题目, 我们保证所有瓜的重量都是一个正偶数。
    现在智乃想要知道, 如果他想要购买西瓜的重量和分别为 $k=1,2,3 \ldots M$ 时, 有多少种购买西瓜的方案, 因为这些数字可能会很大, 请输出方案数对 $10^{9}+7$ 取余数后的结果。

思考

分组背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int n,m,x;
const long long mod=1e9+7;
long long dp[MAXN]; 
int main()
{
    dp[0]=1;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        for(int i=m;i;--i)
        {
            if(i>=x/2)dp[i]+=dp[i-x/2];
            if(i>=x)dp[i]+=dp[i-x];
            while(dp[i]>=mod)dp[i]-=mod;
        }
    }
    for(int i=1;i<=m;++i)
    {
        printf("%lld%c",dp[i]," \n"[i==m]);
    }
    return 0;
}

智乃买瓜(another version)

题意

现在智乃知道, 购买西瓜的重量和分别为 $k=1,2,3 \ldots M$ 时, 购买西瓜的方案的种类数对 $10^{9}+7$ 取余数后的结果。
她想要还原水果摊贩卖的这若干个不同的西瓜重量分别为多少, 请你构造一个贩卖 $N$ 个不同西瓜的水果摊, 其购买西瓜的重量和满足智乃的要求, 当出现有多种符合题目描述的答案时, 你只用输出任意一 种。
我们保证输入的数据至少存在一个 $N \leq 10^{3}$ 的合法解。

思考

看到题目之后很自然的逆向思维, 既然这道题是原题输入输出的倒置。不妨去想, 怎么把放进背包的物品 取出来。
观察题目, 说整只西瓜的质量都是偶数, 那么最终答案为什么会出现质量和为奇数的情况? 显然是由于有 买半个瓜的决策。
那么就可以从小到大逆推, 首先能够知道, $d p[1]$ 的值实际上就是质量为 2 的瓜的数目。
接下来的问题在意，已经知道了整个背包的信息（DP数组），如何把这些质量为 2 的瓜从背包中取出?
观察DP转移方程, 是一个加法和式。

天然的逆向思维, 怎么加上去的, 就怎么减回来。
则有

这样, 我们就得到了原题的逆动态规划转移方程, 倒着来一遍还原即可, 和上一道题一样, 实际处理时习 惯使用滚动数组优化到一维。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int MAXN=1005;
long long dp[MAXN];
int m;
vector<int>ans;
int main()
{
    dp[0]=1;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&dp[i]);
    }
    for(int i=1;i<=m;++i)
    {
        while(dp[i])
        {
            ans.push_back(i*2);
            assert(ans.size()<=1000);
            for(int j=0;j<=m;++j)
            {
                if(j+i<=m)dp[j+i]-=dp[j];
                while(j+i<=m && dp[j+i]<0)dp[j+i]+=mod;
                if(j+i+i<=m)dp[j+i+i]-=dp[j];
                while(j+i+i<=m && dp[j+i+i]<0)dp[j+i+i]+=mod;
            }
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)
    {
        printf("%d%c",ans[i]," \n"[i+1==ans.size()]);
    }
    return 0;
}