BOJ 27212 - 미팅

BOJ 27212 - 미팅

LCS DP 문제이고 점화식은 단순히 $dp[i][j]$를 $i,j$ 번 학생까지 봤을 때 최대 만족도의 합이라고 했을 때,

$$ dp[i][j]=\text{Max}\begin{cases} dp[i-1][j-1]+W[C_i][C_j] \\ dp[i-1][j] \\ dp[i][j-1] \end{cases} $$

이다.

int dp[1002][1002];
void solve() {
   int n, m, c;
   cin >> n >> m >> c;
   vvi w(c + 1, vi(c + 1));
   vi ca(n + 1), cb(m + 1);
   for (int i = 1; i <= c; i++) for (int j = 1; j <= c; j++) cin >> w[i][j];
   fv1(ca);
   fv1(cb);
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         maxa(dp[i][j], dp[i - 1][j]);
         maxa(dp[i][j], dp[i][j - 1]);
         maxa(dp[i][j], dp[i - 1][j - 1] + w[ca[i]][cb[j]]);
      }
   }
   cout << dp[n][m];
}