AOJ - TRIPATHCNT

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;  
}