DDOSvoid's Blog

Luogu P3052 [USACO12MAR]Cows in a Skyscraper G

发表于 分类于
本文字数： 664 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3052

Solution

待更

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 19 
using namespace std;

int n, m, a[maxn]; 

int f[1 << maxn], g[1 << maxn]; 

int main() { 
    cin >> n >> m; int M = (1 << n) - 1; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(f, 10, sizeof f); f[0] = 1; g[0] = m; 
    for (int S = 0; S < M; ++S)
        for (int i = 1; i <= n; ++i) {
            if (S >> i - 1 & 1) continue;
            int T = S | 1 << i - 1, v = a[i] > g[S];
            if (f[T] > f[S] + v) {
                f[T] = f[S] + v;
                g[T] = (v ? m : g[S]) - a[i]; 
            }
            else if (f[T] == f[S] + v)
                g[T] = max(g[T], (v ? m : g[S]) - a[i]);
        }
    cout << f[M] << endl;
    return 0; 
}