T29:Cows in a Skyscr

1）题目意思

有 N 头奶牛要坐电梯下楼。每头奶牛体重 Ci，电梯每次最多承重 W。

你可以把若干头奶牛一起放进一次电梯里，但这次电梯里所有奶牛体重之和不能超过 W。问：把所有奶牛都运下去，最少需要坐几次电梯。

N <= 18，可以用状态压缩 DP。

---

2）思路解析（状态压缩 DP：最少趟数 + 当前趟已用重量）

我们用 mask 表示已经运下去的奶牛集合：

• mask 的第 i 位为 1 表示第 i 头奶牛已经安排好了

对每个 mask，我们记录一个最优状态：

• dp[mask] = (rides, weight)
  • rides：已经用了多少趟电梯
  • weight：当前最后一趟电梯已经放了多少重量（越小越好，方便后面再塞人）

初始：

• dp[0] = (1, 0)

  表示从第 1 趟开始装，当前重量为 0

转移：枚举一个还没装的奶牛 i

• 如果 weight + Ci <= W：可以塞进当前这趟

  新状态是 (rides, weight + Ci)

• 否则：必须开新的一趟

  新状态是 (rides + 1, Ci)

每次取更优的状态，比较规则：

1. rides 更小更优
2. rides 相同，则 weight 更小更优

答案是 dp[(1<<N)-1].rides。

复杂度：

• 状态数 2^N，每个状态枚举 N 个奶牛
• N<=18，可以通过

---

3）代码

#include <bits/stdc++.h>
using namespace std;

struct State{                                            // 定义dp状态
    int rides;                                           // 已用电梯趟数
    long long w;                                         // 当前最后一趟已用重量
};

bool better(const State &a,const State &b){              // 比较两个状态谁更优
    if(a.rides!=b.rides) return a.rides<b.rides;         // 趟数更少更优
    return a.w<b.w;                                      // 趟数相同则当前重量更小更优
}

int main(){                                              // 主函数入口
    ios::sync_with_stdio(false);                         // 加速输入输出
    cin.tie(nullptr);                                    // 加速输入输出

    int N;                                               // 奶牛数量
    long long W;                                         // 电梯承重上限
    cin>>N>>W;                                           // 读入N和W

    static long long C[18];                              // 存每头奶牛体重
    for(int i=0;i<N;i++) cin>>C[i];                      // 读入体重

    int FULL=(1<<N)-1;                                   // 所有奶牛都安排好的mask

    static State dp[1<<18];                              // dp[mask]存最优状态
    for(int mask=0;mask<=FULL;mask++){                   // 初始化dp为很差的状态
        dp[mask].rides=1e9;                              // 趟数设很大
        dp[mask].w=0;                                    // 重量随便设
    }

    dp[0].rides=1;                                       // 初始从第1趟开始装
    dp[0].w=0;                                           // 当前重量为0

    for(int mask=0;mask<=FULL;mask++){                   // 枚举所有mask
        State cur=dp[mask];                              // 取当前最优状态
        if(cur.rides==1e9) continue;                     // 不可达就跳过（理论上不会）

        for(int i=0;i<N;i++){                            // 尝试把第i头奶牛加入
            if(mask&(1<<i)) continue;                    // 已经在mask里则跳过

            int nmask=mask|(1<<i);                       // 新mask：加入第i头奶牛
            State nxt;                                   // 新状态

            if(cur.w + C[i] <= W){                       // 如果还能塞进当前这趟
                nxt.rides=cur.rides;                     // 趟数不变
                nxt.w=cur.w + C[i];                      // 当前趟重量增加
            }else{                                       // 否则需要开新的一趟
                nxt.rides=cur.rides + 1;                 // 趟数+1
                nxt.w=C[i];                              // 新一趟当前重量就是这头奶牛
            }

            if(better(nxt,dp[nmask])) dp[nmask]=nxt;     // 若更优则更新dp
        }
    }

    cout<<dp[FULL].rides<<endl;                          // 输出最少电梯趟数
    return 0;                                            // 程序结束
}