智乃买瓜(another version)

思路

• $ii$从1到m枚举dp数组,
• 如果$dp[1]>0dp[1]>0$, 说明有$dp[1]dp[1]$个重量为2的瓜, 因为重量和为1的方案只能由1个重量为2的瓜买一半得到。 对dp数组中的每一项, 消除重量为2的瓜的影响, 也就是$dp[i-1][j]=(dp[i][j]-dp[i-1][j-2]-dp[i-1][j-2\mathrm{/}2])\mathrm{\%}moddp[i-1][j]=(dp[i][j]\; -\; dp[i-1][j-2]-dp[i-1][j-2/2])\backslash \%\; mod$
• 消除重量为2的瓜之后, 若$dp[2]>0dp[2]>0$, 则说明有$dp[2]dp[2]$个重量为$2\ast 22*2$的瓜，因为重量为2的瓜已经清除了，所以重量和为2只能是买半个重量为4的瓜。再让j从1到m遍历dp数组, 来消除重量为4的瓜对方案数的影响, 状态转移方程:$dp[i-1][j]=(dp[i][j]-dp[i-1][j-4]-dp[i-1][j-4\mathrm{/}2])\mathrm{\%}moddp[i-1][j]=(dp[i][j]\; -\; dp[i-1][j-4]-dp[i-1][j-4/2])\backslash \%\; mod$
• 以此类推, 从小到大第一个大于0的$dp[i]dp[i]$说明有$dp[i]dp[i]$个重量为$2\ast i2*i$的瓜
• 每次消除重量为$w_{i}w\_i$的瓜对方案数的影响，状态转移方程为$dp[i-1][j]=(dp[i][j]-dp[i-1][j-w_i]-dp[i-1][j-w_i\mathrm{/}2])\mathrm{\%}moddp[i-1][j]=(dp[i][j]\; -\; dp[i-1][j-w\_i]-dp[i-1][j-w\_i/2])\backslash \%\; mod$, 优化成一维：$dp[j]=(dp[j]-dp[j-w_i]-dp[j-w_i\mathrm{/}2])\mathrm{\%}moddp[j]=(dp[j]\; -\; dp[j-w\_i]-dp[j-w\_i/2])\backslash \%\; mod$，$jj$从小到大枚举

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e3 + 10, mod = 1e9 + 7;
int n, m;
int f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> f[i];
    }
    f[0] = 1;
    vector<int> ans;

    for (int i = 1; i <= m; i++)
    {
        while (f[i])
        {
            ans.push_back(i * 2);
            for (int j = 1; j <= m; j++)
            {
                if (j - i >= 0)
                    f[j] = (f[j] - f[j - i] + mod) % mod;
                if (j - 2 * i >= 0)
                    f[j] = (f[j] - f[j - 2 * i] + mod) % mod;
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto i : ans)
    {
        cout << i << ' ';
    }
    return 0;
}