洛谷/USACO “破锣摇滚”乐队 Raucous Rockers

洛谷题号:P2736
又是动规,只会DFS……

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
int n, t, m;
int song[25];
int dfs(int cur_song, int cur_cd, int rem_min){
    if (cur_song == n + 1){
        if (cur_cd <= m){
            return 0;
        }
        return -2e9;
    }
    if (song[cur_song] <= rem_min){
        return max(dfs(cur_song + 1, cur_cd, rem_min), dfs(cur_song + 1, cur_cd, rem_min - song[cur_song]) + 1);
    }
    else{//song[cur_song]>rem_min
        return max(dfs(cur_song + 1, cur_cd, rem_min), dfs(cur_song + 1, cur_cd + 1, t - song[cur_song]) + 1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> t >> m;
    for (int i = 1; i <= n; i++){
        cin >> song[i];
        if (song[i] > t){
            i--;
            n--;
        }
    }
    if (n == 0){
        cout << 0 << endl;
        return 0;
    }
    cout << dfs(1, 1, t) << endl;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注