题解：CF2028F Alice's Adventures in Addition

· · 题解

题目传送门

题目思路

根据题意，表达式要按照正常的顺序进行计算，即先乘后加。因此，表达式可以看成若干项乘积进行求和。所以，我们从左往右处理数字时，要同时维护两个值：

  1. 当前段的乘积，记为 c。
  2. 当前位置不包括该项已经确定的总和，记为 s。

那么我们可以定义 dp 数组：dp_i=msk 表示当前该项的乘积为 i 时，若 msk 的第 j 项为 1，则存在前缀和为 j 的状态。由于 msk 只由 0 和 1 组成，所以可以用 bitset 优化存储，减小空间和时间的消耗。

由于 m \le 10^4，所以超过 m 的和与乘积都不需要记录，直接跳过即可。

接下来考虑如何进行状态转移。假设当前已经处理完前 i-1 个数，正在处理第 i 个数 x。

如果我们选择乘法，那么就将当前该项的乘积乘上 x。由于前面已经确定的和不变，所以直接将当前的状态复制到新的 bitest 状态中。

如果我们选择加法，结算当前的乘积 c，加到前面的和中，从当前开始是新的乘法段，新的和就是状态 bs \ll c，即原来旧的总和加上 c，更新状态 msk，保留小于等于 m 的位。

初始化将第一个数 a_1 作为乘积 c 的初值，前缀和 s=0，所以 dp_{a_1} 只有第 0 位为 1，其他全部为 0。若 a_1 > m 则用最大值 10005 标记。

而最后的答案可以这样计算：遍历所有状态，如果一个状态中 c \le m 并且状态的第 m-c 位为 1，即存在方法可以使前缀和为 m-c，那么总和就恰好为 m，直接输出 Yes。

如果遍历完所有状态仍然没有合法方案，输出 No。

code

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[200005];
bitset<10005>msk,st;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        if(n==1)
        {
            if(a[1]==m)cout<<"YES\n";
            else cout<<"NO\n";
            continue;
        }
        msk.reset();
        for(int i=0;i<=m;i++)
            msk.set(i);
        map<int,bitset<10005>>dp;
        int sc=a[1];
        st.reset();
        st.set(0);
        dp[sc]=st;
        for(int i=2;i<=n;i++)
        {
            int x=a[i];
            map<int,bitset<10005>>cur;
            for(auto p:dp)
            {
                int c=p.first;
                bitset<10005>bs=p.second;
                int curm=0;
                if(x!=0)
                {
                    long long v=1ll*c*x;
                    if(v>m)curm=10005;
                    else curm=v;
                }
                cur[curm]|=bs;
                int mul=x;
                cur[mul]|=(bs<<c)&msk;
            }
            dp=move(cur);
        }
        bool flag=false;
        for(auto p:dp)
        {
            int c=p.first;
            bitset<10005>bs=p.second;
            if(m>=c&&bs[m-c])
            {
                flag=true;
                break;
            }
        }
        if(flag)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}