AOJ - TRIPATHCNT
삼각형의 최대의 경로의 수를 세준다.
$dp[y][x]=$ $y,~x$ 에서 $y=n-1$ 까지 갈 때 <점수의 최대값, 경로의 개수> 를 관리해준다.
그리고 $y=n-1$ 에서 점수의 최대값을 보고, 그것들의 개수를 모두 더한것이 정답이다.
const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
void solve() {
int n;
cin >> n;
vvi b(n, vi(n));
for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) cin >> b[i][j];
vector<vector<pi>> dp(n, vector<pi>(n));
dp[0][0] = {b[0][0], 1};
for (int y = 1; y < n; y++) {
for (int x = 0; x <= y; x++) {
dp[y][x] = max(dp[y][x], {dp[y - 1][x].fi + b[y][x], dp[y - 1][x].se});
if (x) {
if (dp[y - 1][x - 1].fi > dp[y - 1][x].fi) {
dp[y][x] = max(dp[y][x], {dp[y - 1][x - 1].fi + b[y][x], dp[y - 1][x - 1].se});
} else if (dp[y - 1][x - 1].fi == dp[y - 1][x].fi) {
dp[y][x].se += dp[y - 1][x - 1].se;
}
}
}
}
int mx = 0;
for (int i = 0; i < n; i++) {
mx = max(mx, dp[n - 1][i].fi);
}
int ans = 0;
for (int i = 0; i < n; i++) if (dp[n - 1][i].fi == mx) ans += dp[n - 1][i].se;
cout << ans << endl;
}
Comments