题解：B4093 [CSP-X2021 山东] 发送快递

· · 题解

题目传送门

初步思考

看了看题面，可以知道这应该是一道状态压缩 dp 的模版题，先不管题目中的限制条件，反正这一定是一道状态压缩 dp 的题目。不妨先假设 s 等于 0，此时就是一道纯状态压缩 dp 的题目，那我们就先考虑状态压缩 dp。

具体步骤

确定状态

用一个结构体存储数组 dp，再定义状态 S 为要处理哪些书，此时的 dp 数组有两个量。其中第一个量是 x，代表在状态 S 下最少需要几个包裹。还有一个量是 t，代表在 x 最小的情况下，最空的包裹已经用了多少容量。其中 dp_S 表示在状态 S 下使这两个量最优。\\
具体的，定义 x 和 t 这两个量最优，设最优的 x 和 t 为 sx 和 st，满足在状态 S 下，\forall x 和 \forall t 都不满足 x<sx \lor x=sx \land t<st。\\

状态转移

设函数 \operatorname{cmp} 会在两个状态中返回较优的状态，其中，一个状态是否最优取决于状态中的两个量是否最优。

方程推导

想象一下，我们要在原来的状态中新添加一本书，那我们肯定是要把它放进最空的包裹里，如果连最空的包裹都放不下，那就只能新建一个包裹来放了，所以我们可以计算出新状态，公式如下：

oldS_t+a_i>m ,&oldS_x+1 \\ oldS_t+a_i\le m,&oldS_x \\ \end{cases} \\ oldS_t+a_i>m ,&a_i \\ oldS_t+a_i\le m,&oldS_t+a_i \\ \end{cases}

其中 i\in S，oldS 表示老状态，newS 表示新状态。 \\ 那么状态转移方程就显而易见了，每次枚举 i 时算出新状态，再将所有的新状态取最优。

状态转移方程

dp_S=\operatorname{cmp}(dp_S,dp_{newS})

示例

样例输入：

3 10
4 8 2

此时的 dp 数组如下：

状态S 最优答案
0 0 1（1） 1.4
0 1 0（2） 1.8
0 1 1（3） 2.4
1 0 0（4） 1.2
1 0 1（5） 1.6
1 1 0（6） 1.10
1 1 1（7）

格式说明：最优答案用 x.t 这样的格式表示。

\\

现在我们已经知道了状态 7 之前的所有状态的最优答案，现在我们要算出状态 7 的最优答案，通过枚举 7 的所有二进制位，我们可以知道状态 7 可以由状态 6，5，3 转移而来，可分为三组计算，分别为（1.10，4），（1.6，8），（2.4，2）。根据新状态计算公式，可得计算结果分别为 2.4，2.8，2.6。其中最优的答案是 2.4。这里只做一个示例，你们可以自己动手试一下，算一算，加深理解。

\\

到目前为止，主要问题其实已经解决了。但还剩下一个问题，那就是 s\ne 0 的情况。这个问题其实很简单，只需要并查集统计需要打包在一起的书，将它们的质量都加起来然后合并成一本书就行啦！

代码

其实我讲的应该算清晰了的，你们可以先自己试试，不懂的再看代码。

#include<bits/stdc++.h> 
using namespace std;
int n1,m,a1[25],s,num,n,a[25],fnum;
int f[25];
int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
bool cmp(int x1,int y1,int x2,int y2)
{
    if(x1==y1) return x2>y2;
    return x1>y1;
}
struct{
    int x,t;
}dp[1<<23];
int main()
{
    cin>>n1>>m;
    for(int i=1;i<=n1;i++) f[i]=i;
    for(int i=1;i<=n1;i++) cin>>a1[i];
    cin>>s;
    while(s--)
     {
        cin>>fnum;
        if(cin.get()=='\n') continue;//若输入的是换行，跳过。 
        while(cin>>num)
         {
            f[find(num)]=find(fnum);//并查集。  
            if(cin.get()=='\n') break;//同上。 
         }
     }
    for(int i=1;i<=n1;i++)
     if(f[i]!=i)
      {
        a1[f[i]]+=a1[i];
        a1[i]=0;
      }
    for(int i=1;i<=n1;i++)
     if(a1[i]) a[++n]=a1[i];
/*  并查集部分还是很好理解的，这里不再过多赘述。*/ 

/*----------------------DP----------------------*/

    for(int i=1;i<=n;i++)
     {
        dp[(1<<i-1)].x=1;
        dp[(1<<i-1)].t=a[i];
     }
    //初始化，应该不用多讲了吧。 
    for(int s=1;s<(1<<n);s++)
     {      
        if(!(s&s-1)) continue;
        dp[s].x=INT_MAX;//一定要赋初值！ 
        for(int i=1;i<=n;i++)   
         if((s>>i-1)&1)
          {
            int x=dp[s^(1<<i-1)].x;
            int t=dp[s^(1<<i-1)].t;
            if(t+a[i]>m)
             {
                x++;
                t=a[i]; 
             }
            else t+=a[i];
            if(cmp(dp[s].x,x,dp[s].t,t))
             {
                dp[s].x=x;
                dp[s].t=t;  
             }
          }
     }
    cout<<dp[(1<<n)-1].x;
    return 0;
}