[AtCoder] ABC 165 C – Many Requirements
問題
方針
全ての数列のパターンに対して得点を求めます。どのように数列を生成するかですが、深さ優先探索を行います。条件を満たす数列が \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません