[AtCoder] ABC 165 C – Many Requirements

2020年12月14日

問題

方針

全ての数列のパターンに対して得点を求めます。どのように数列を生成するかですが、深さ優先探索を行います。条件を満たす数列が \( i \) 番目まで決まっているとき、\( A_{i + 1} \) の値は、\( A_{i} \leq A_{i+1}\leq M \) となります。つまり、\( i + 1\) 番目の深さで分岐する探索は、\( M – A_{i} + 1 \) 個あります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M, Q;
int A[11]{};
int a[50], b[50], c[50], d[50];

int ans = 0;

void dfs(int n) {
    if (n == N) {
        int sum = 0;
        for (int i = 0; i < Q; i++) {
            if (A[b[i]] - A[a[i]] == c[i]) sum += d[i];
        }
        ans = max(ans, sum);
        return;
    }
    for (int i = min(A[n], M); i <= M; i++) {
        A[n + 1] = i;
        dfs(n + 1);
    }

}
int main() {
    cin >> N >> M >> Q;

    for (int i = 0; i < Q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    A[0] = 1;
    dfs(0);
    cout << ans << "\n";
    return 0;
}