rainman's blog

学海无涯,回头是岸

题解 P1441 【砝码称重】

对 @hsfzLZH1 题解的小部分纠正与补充说明

RT。目前 @hsfzLZH1 的题解得票最高,讲解也十分到位,在此表示感谢。然而,在 @hsfzLZH1 的题解里,有微小的细节没有处理好。


状态转移方程

原题解: $f[i][j]=f[i-a[i]][j-1]$ , 事实上,应为: $f[i][j]=f[i-a[j]][j-1]||f[i][j-1]$ ,其中 $||$ 表示逻辑运算“或”。

说明

  • :类比于背包问题,有“选与不选”的两种方案。此时 $f[i-a[j]][j-1]$ 表示选择第 $j$ 件物品,而 $f[i][j-1]$ 表示不选择第 $j$ 件物品。如果这两者中有一个成立,就可以使得在前 $j$ 件物品中,存在一种方案使得砝码重量达到 $i$ ,所以是逻辑运算“或”。

  • @hsfzLZH1 的题解里有可能是笔误,也有可能是数据有点水。


关于数组下标问题

@hsfzLZH1 的题解数组下标是从零开始的,这里提供一种下标从一开始的 $dfs$ 过程:

void dfs(int certain,int deserted)
{
    if(deserted>m)return;
    if(certain==n)
    {
        if(deserted==m)  //dp
        {
            memset(f,false,sizeof(f));
            f[0]=true;int cnt=0;  //init
            for(int j=1;j<=n;j++)
            {
                if(vis[j])continue;
                for(int i=n*100;i>=a[j];i--)
                f[i]=f[i-a[j]]||f[i];
            }
            for(int w=1;w<=n*100;w++)
            if(f[w])cnt++;
            ans=max(ans,cnt);
        }
        return;
    }

    dfs(certain+1,deserted);
    vis[certain+1]=true;
    dfs(certain+1,deserted+1);
    vis[certain+1]=false;
}

2018-08-03 15:20:25 in 题解