[洛谷2736] “破锣摇滚”乐队 Raucous Rockers

Link: P2736 “破锣摇滚”乐队 Raucous Rockers - 洛谷

这道题没什么难度,我只是想说裸的DFS明明可以AC。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 21;
int n, t, m, ans = -1, a[maxn], f[maxn];
void DFS(int i, int j, int cnt) {
    if (i > n || j > m) {
        if (cnt > ans)
                    ans = cnt;
        return ;
    }
    DFS(i + 1, j, cnt);
    if (j < m && a[i] <= t) {
        f[j + 1] = a[i];
        DFS(i + 1, j + 1, cnt + 1);
        f[j + 1] = 0;
    }
    if (f[j] + a[i] <= t) {
        f[j] += a[i];
        DFS(i + 1, j, cnt + 1);
        f[j] -= a[i]; 
    }
}
int main() {
    scanf("%d%d%d", &n, &t, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    DFS(1, 1, 0);
    printf("%d\n", ans);
    return 0;
}
添加新评论

0%