Elevator Rides (CSES 1653)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 315 所需閱讀時間 ≈ 1 分鐘

題目網址

There are n people who want to get to the top of a building which has only one elevator. You know the weight of each person and the maximum allowed weight in the elevator. What is the minimum number of elevator rides?

解題思路：

位元 DP，分別記錄該狀態下最少搭乘次數以及在最少搭乘次數下的最輕的電梯重量，DP 轉移式在下方程式碼中的註解

Elevator Rides
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i<=b; ++i)
#define rev(i, a, b) for(int i = a; i>=b; --i)
#define tomax(a, b) (a)=max((a),(b))
#define tomin(a, b) (a)=min((a),(b))
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
// dp[i][0] : minimum rides
// dp[i][1] : minimum weight
 
// init
// dp[i][0] = n
// dp[i][1] = INT_MAX
// dp[0][0] = 1, dp[0][1] = 0
 
// dp[i][0]_ori = dp[i][0]
// new_weight = dp[i^(1<<j)][1] + w[j]                        , j in i
// dp[i][0] = min(dp[i][0], dp[i^(1<<j)][0]+(new_weight>x))   , j in i
// dp[i][1] = min(dp[i][1], new_weight)                       , dp[i][0]==dp[i][0]_ori && new_weight<=x
// dp[i][1] = new_weight                                      , dp[i][0]<dp[i][0]_ori  && new_weight<=x
// dp[i][1] = w[j]                                            , dp[i][0]<=dp[i][0]_ori && new_weight>x
 
int dp[1<<21][3];
int n, w[22], x;
 
signed main(){
    ios;
    cin >> n >> x;
    rep(i, 0, n-1) cin >> w[i];
    rep(i, 0, 1<<n)
        dp[i][0]=n, dp[i][1]=INT_MAX;
    dp[0][0] = 1, dp[0][1] = 0;
    rep(i, 1, (1<<n)-1){
        rep(j, 0, n-1){
            if(i & (1<<j)){
                int new_weight = (dp[i^(1<<j)][1]) + w[j];
                if(dp[i][0] >= dp[i^(1<<j)][0]+(new_weight>x)){
                    if(dp[i][0] == dp[i^(1<<j)][0] && (new_weight<=x))
                        dp[i][1] = min(dp[i][1], new_weight);
                    else dp[i][1] = new_weight>x ? w[j] : new_weight;
                    dp[i][0] = dp[i^(1<<j)][0]+(new_weight>x);
                }
            }
        }
    }
    cout << dp[(1<<n)-1][0] << '\n';
    return 0;
}

P.S.
這題我原本一開始把 \(dp[i][0]\) 設成 \(x\)，debug 了一個多小時… 另外這是我第一次寫位元 dp 感覺超酷的～