ABC 165 C - Many Requirements

ABC 165 C - Many Requirements についてのメモを残します。

再帰関数

• 問題 : ABC 165 C - Many Requirements

数列 は、項数が であり、 を満たす。条件を満たす数列 の総数は、 個の仕切りと 個のボールの並べ方の総数と同じで、 通り。

実装は再帰関数を用いた。

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

int N, M, Q;
vector<int> a(50), b(50), c(50), d(50);
int ans = 0;

void dfs(int n, vector<int> A, int tail) {
  if (n == N) {
    int tmp = 0;
    for (int i = 0; i < Q; i++) {
      if (A.at(b.at(i)) - A.at(a.at(i)) == c.at(i)) {
        tmp += d.at(i);
      }
    }
    ans = max(ans, tmp);
    return;
  }
  for (int i = tail; i <= M; i++) {
    A.at(n) = i;
    dfs(n+1, A, i);
  }
}

int main() {
  cin >> N >> M >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
    a.at(i)--; b.at(i)--;
  }
  vector<int> A(N);
  dfs(0, A, 1);
  cout << ans << endl;
}