AOJ 0574 - Nails

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0574

解法

\((i, j)\) の位置にサイズ \(X\) の輪ゴムがあるとき、\((i+1, j)\) の位置と \((i+1, j+1)\) の位置にサイズ \(X-1\) の輪ゴムがあるとみなすことができる。

よって、これを DP 的に左上のほうから更新していき、サイズ 1 以上の輪ゴムに囲われている釘の数を数えればよい。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, M;
 8   scanf("%d %d", &N, &M);
 9   static int a[5001][5001];
10   for (int i = 0; i < M; i++) {
11     int A, B, X;
12     scanf("%d %d %d", &A, &B, &X);
13     a[A][B] = X+1;
14   }
15 
16   int ans = 0;
17   for (int i = 1; i <= N; i++) {
18     for (int j = 1; j <= i; j++) {
19       a[i][j] = max(a[i][j], a[i-1][j] - 1);
20       a[i][j] = max(a[i][j], a[i-1][j-1] - 1);
21       if (a[i][j] > 0) {
22         ++ans;
23       }
24     }
25   }
26   printf("%d\n", ans);
27   return 0;
28 }