题解 CF71E 【Nuclear Fusion】

· · 题解

本题题意为: 求一组数能不能其中几个相加得出另一组数。

发现数据很小，于是想到状压。

然后dfs枚举状态。 一开始用打表的方法把原子符号变为数字。dfs(tot,sum,q)表示目前完成了tot个原子，目前原子序数累加的和，用q来表示a数组各元素取或不取。枚举原子a[i]。如果没有取过，就dfs取这个原子。

加个记忆化，比dp跑得快多了 code:

#include<bits/stdc++.h>
using namespace std;
const int N=25;
string names[] = {" ","H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar","K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu","Zn" ,"Ga", "Ge", "As" ,"Se" ,"Br" ,"Kr" ,"Rb" ,"Sr" ,"Y" ,"Zr" ,"Nb", "Mo" ,"Tc" ,"Ru" ,"Rh" ,"Pd" ,"Ag" ,"Cd" ,"In" ,"Sn" ,"Sb" ,"Te" ,"I" ,"Xe" ,"Cs", "Ba" ,"La", "Ce" ,"Pr" ,"Nd" ,"Pm" ,"Sm", "Eu" ,"Gd", "Tb" ,"Dy" ,"Ho" ,"Er" ,"Tm" ,"Yb" ,"Lu", "Hf" ,"Ta", "W", "Re", "Os" ,"Ir" ,"Pt" ,"Au", "Hg", "Tl", "Pb", "Bi" ,"Po" ,"At", "Rn" ,"Fr", "Ra" ,"Ac" ,"Th" ,"Pa", "U" ,"Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es" ,"Fm"};
int n,k,flag;
int a[N],b[N];
bool f[105][140000];
vector<int> ans; 
int getid(string x) {
    for(int i=1;i<=100;i++)
    if(names[i]== x) return i;
}
string getst(int i) {
    return names[i];
}
void mprint(){
    int sum=0,j=0;
    for(int i=0;i<ans.size();i++){
        sum+=ans[i];
        cout<<getst(ans[i]);
        if(sum==b[j]){
            printf("->");
            cout<<getst(b[j++]);
            printf("\n");
            sum=0;
        }
        else printf("+");
    }
}
void dfs(int tot,int sum,int q){
    if(sum==b[tot]){
        if(tot==k) {
            flag=1;
            printf("YES\n");    
            mprint();
        }
        else dfs(tot+1,0,q);//下一个
    }
    if(sum>b[tot]) return;//减枝
    if(f[tot][q]) return;//记忆化
    for(int i=0;i<n&&(!flag);i++){
        if(q&(1<<i)) continue;
        else {
            ans.push_back(a[i]);
            dfs(tot,sum+a[i],q|(1<<i));
            ans.pop_back();//回溯
        }
    }
    f[tot][q]=1；
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        string s;cin>>s;
        a[i]=getid(s);
    }
    for(int i=0;i<k;i++){
        string s;cin>>s;
        b[i]=getid(s);
    }
    dfs(0,0,0);
    if(!flag) printf("NO");
    return 0;
}