以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q 個のクアドラプレット(4 要素タプル)が与えられる.i 番目のクアドラプレットは (ai,bi,ci,di) である.
また,整数 N,M が与えられる.以下の条件を満たす数列 {Ai} を考える.
|A|=N
1≤A1≤A2≤⋯≤AN≤M
この数列 A の「得点」を,
Abi−Aai=ci を満たすようなクアドラプレットについての di の総和
とする.
可能な数列の内,得点が最大のものの得点を求めよ.
制約
2≤N≤10
1≤M≤10
1≤Q≤50
ai,bi,ci は意味を成す値
1≤di≤105
コード
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, s, n) for (int i = (s); i > (int)(n); i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define sz(x) ((int)(x).size())
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T & a, const T & b) { if (b < a) { a = b; return 1; } return 0; }
int N, M, Q;
int a[50], b[50], c[50], d[50];
int Max = 0;
void func(string A) {
if (sz(A) == N) {
int score = 0;
rep(i, Q) {
if (A[b[i] - 1] - A[a[i] - 1] == c[i]) score += d[i];
}
chmax(Max, score);
return;
}
int last = 1;
if (sz(A) >= 1) last = A[sz(A) - 1];
rep2(i, last, M + 1) {
string nA = A;
nA += ('0' + i);
func(nA);
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> M >> Q;
rep(i, Q) cin >> a[i] >> b[i] >> c[i] >> d[i];
string A = "";
func(A);
cout << Max << "\n";
return 0;
}
void func(string A)
としている部分ですが、正整数列であると定義されているA
がなぜか string 型になっています。そのため、nA += ('0' + i);
の結果(nA
の値)が49
とか50
になっています。なので、これを較正するためにif (sz(A) >= 1) last = A[sz(A) - 1];
をif (sz(A) >= 1) last = A[sz(A) - 1] - '0';
とする必要があります。