백준14305 Stretch Rope (Large)

작성일 | In

문제 링크

  • http://icpc.me/14305

사용 알고리즘

  • DP
  • 세그먼트 트리

풀이

배낭의 무게가 $[A_i, B_i]$라는 구간으로 표현되는 0/1 냅색 문제입니다.
$D(i, j)$를 i번째 물건까지 고려했을 때, 무게의 합이 j가 되는 최소 가치로 정의해서 DP를 하면 됩니다.

상태 전이를 생각해봅시다.
무게의 합이 j가 되기 위해서는, 기존 무게가 $[j-B_i, j-A_i]$ 범위에 있어야 합니다. 그러므로 Deque나 Segment Tree 등으로 구간의 최솟값을 구하면 시간 내에 문제를 풀 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 0x3f3f3f3f3f3f3f3f;

ll tree[1 << 15];
const int sz = 1 << 14;
void update(int x, ll v){
    x |= sz; tree[x] = v;
    while(x >>= 1) tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
ll query(int l, int r){
    l |= sz; r |= sz; ll ret = inf;
    while(l <= r){
        if(l & 1) ret = min(ret, tree[l++]);
        if(~r & 1) ret = min(ret, tree[r--]);
        l >>= 1; r >>= 1;
    }
    return ret;
}

int n, m, l;
ll s[1010], e[1010], x[1010], dp[2][10101];

void solve(int tc){
    cout << "Case #" << tc << ": ";
    memset(tree, 0x3f, sizeof tree);
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> m >> l;
    for(int i=1; i<=n; i++) cin >> s[i] >> e[i] >> x[i];

    dp[0][0] = 0; update(0, 0);
    for(int i=1; i<=n; i++){
        for(int j=0; j<=l; j++) dp[i&1][j] = dp[i-1&1][j];
        for(int j=0; j<=l; j++){
            int S = j - e[i], E = j - s[i];
            if(E < 0) continue; S = max(0, S);
            dp[i&1][j] = min(dp[i&1][j], query(S, E) + x[i]);
        }
        for(int j=0; j<=l; j++) update(j, dp[i&1][j]);
    }
    if(dp[n&1][l] <= m) cout << dp[n&1][l] << "\n";
    else cout << "IMPOSSIBLE" << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; for(int i=1; i<=t; i++) solve(i);
}