CF1552D题解
思路
首先，$a_i$ 的正负不重要，如果 $a_i=b_j-b_k$，那么就有 $-a_i=b_k-b_j$，读入时将 $a_i$ 全部转化为正数。
若满足 $a_i+a_j+\ldots+a_k$，那么就可以构造出 $b$ 序列，否则不行。
从左到右遍历一遍 $a$ 序列，动态规划推出所有可以组成的和，并判断是否满足上式，时间复杂度 $O(T\times n\times \max(a_i))$。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T,n,dp[N],a[20];
void solve(){
for(int i=0;i<N;i++) dp[i]=0;
cin>>n; dp[0]=1; bool flag=false;
for(int i=0;i<n;i++){ cin>>a[i]; a[i]=a[i]<0?-a[i]:a[i]; }
for(int i=0;i<n;i++)
for(int j=N-1-a[i];j>=0;j--)
if(dp[j]){
if(dp[j+a[i]]==1) flag=true;
else dp[j+a[i]]=1;
}
cout<<(flag?"YES\n":"NO\n");
}
-
signed main(){
ios::sync_with_stdio(false);
for(cin>>T;T;T--) solve();
}
现在抛出一个不难验证的结论：若 $a_i;\mathcal{op};a_j;\mathcal{op}\ldots;a_k;\mathcal{op} ;a_l=0$ （$op$ 为 $+$ 或 $-$ ）
那么就可以构造出序列 $b$，否则不能。
那么对于 $a$ 序列中的所有数，有三种情况：
- $a_i$ 不在上面式子中。
- $a_i$ 在上式中，$op$为 $+$。
- $a_i$ 在上式中，$op$ 为 $-$。
共 $3^n-1$ 种状态（因为不能全部不在上式中，所以减去 $1$ 种情况）。
遍历 $1$ 次这种状态，若有一种情况符合上式，那么就输出 yes，时间复杂度 $O(n\times3^n)$。
#include<bits/stdc++.h>
using namespace std;
int T,n,a[20];
void solve(){
cin>>n; int k=pow(3,n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<k;i++){
int sum=0,tk=i;
for(int j=0;j<n;j++){
int s=tk%3; tk/=3;
if(s==2) s=-1;
sum+=s*a[j];
}
if(sum==0) return (void)(cout<<"YES\n");
}
cout<<"NO\n";
}
signed main(){
ios::sync_with_stdio(false);
for(cin>>T;T;T--) solve();
}