CF-339C

65/100​

题意：

现在有一个天平，现有$1\sim10g$的砝码无限个，一个二进制字符串，每一位表示你是否有$ig$的砝码，重复操作，左边放一个，右边放一个，满足以下规则：放哪一边，当前的砝码重量总和要大于另一边，且不能连续放相同质量的砝码，问是否能放完$m$个砝码。

题解：

可以采取建图的方式，即图中每个点看做一个三元组$(i,j,k)$，分别表示，当前放的砝码重量，左边和右边的重量之差，当前回合数，然后看$(0,0,0)$是否能到$(x,y,m)$。更简单的方法是记忆化搜索，令$delt$为当前回合边与另一边的总量差，观察可以发现不管当前回合放哪里，下一回合与另一边的重量差是$x-delt$，很容易发现$delt<=0$是非法状态，搜下去即可。

$AC$代码：

string s;
int m;
int ans[1005];
int vis[1005][15][15];
int dfs(int delt,int la,int x){
  if(x&&delt<=0)return 0;
  if(x>=m){
    cout<<"YES\n";
    _for(int,i,0,m)cout<<ans[i]<<' ';
    return 1;
  }
  if(vis[x][delt][la])return 0;
  vis[x][delt][la]=1;
  _for(int,i,1,11){
    if(s[i-1]=='1'&&la!=i){
      ans[x]=i;
      if(dfs(i-delt,i,x+1))return 1;
    }
  }
  return 0;
}
int main(){
    cin>>s>>m;
    if(!dfs(0,0,0))cout<<"NO";
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2021/06/15/CF-339C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！