POJ 1609 - Tiling Up Blocks

http://poj.org/problem?id=1609

概要

n 個のブロックが与えられる． 各ブロックの上側には，左側に l 個，中央に m 個のでっぱりあり，下側にも同様に左側に l 個，中央に m 個のくぼみがある．

(l, m) のブロックは (l', m') のブロックの上に l >= l' && m >= m' のときに限り積み上げることができる． このとき，最大で何個のブロックを積み上げることができるかを答える．

制約

• n <= 10000
• 1 <= l, m <= 100

解法

dp[i][j] = 左側に i 個，右側に j 個なブロックを一番下にしたときの最大の高さ

という DP．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     static int a[100][100];
10     for (int i = 0; i < 100; i++) {
11       fill_n(a[i], 100, 0);
12     }
13     for (int i = 0; i < N; i++) {
14       int l, m;
15       scanf("%d %d", &l, &m);
16       ++a[l-1][m-1];
17     }
18 
19     static int dp[100][100];
20     for (int i = 0; i < 100; i++) {
21       fill_n(dp[i], 100, 0);
22     }
23     dp[0][0] = a[0][0];
24     for (int j = 1; j < 100; j++) {
25       dp[0][j] = dp[0][j-1] + a[0][j];
26     }
27     for (int i = 1; i < 100; i++) {
28       dp[i][0] = dp[i-1][0] + a[i][0];
29     }
30     for (int i = 1; i < 100; i++) {
31       for (int j = 1; j < 100; j++) {
32         dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
33       }
34     }
35     printf("%d\n", dp[99][99]);
36   }
37   puts("*");
38   return 0;
39 }