AOJ0574 Nails

問題リンク Nails

• 解法

2次元int型配列 t[i][j]を用意します。t[i][j]は(i, j)を上の頂点とする「よい正三角形」の中で最も長い1辺の値が入っているとします。「よい三角形」が無い場合は負の値とします。初期値は-1です。サンプル入力では、
t[2][2] = 1
t[2][1] = 3
という情報が得られます。でもt[2][1]について分解していくと、
t[3][1] = t[3][2] = 2
t[4][1] = t[4][2] = t[4][1] = 1
t[5][1] = t[5][2] = t[5][3] = t[5][4] = 0
ということもわかります。t[5][1]等について0というのは便宜上(5, 1)が「よい三角形」に含まれていることを示します。(i, j)が複数の輪ゴムによって囲まれている場合、t[i][j]が最も大きくなるような値をとれば正しい解が求まります。そして、t[i][j]の値を決めるためには、それ自身の値と、すぐ上の段の2つの座標だけを参照すれば求まります。すなわち、
t[i][j] = max{t[i][j], t[i-1][j]-1, t[i-1][j-1]-1}
です。-1をしているのは1段下がることによって正三角形が小さくなるからです。
配列tは一番上から決定していけばよいです。t[i][j]を順に求めていき、t[i][j]が0以上の値になった回数が解となります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Nails
public class AOJ0574 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		int[][] t = new int[n+1][];
		for(int i=0;i<=n;i++){
			t[i] = new int[i+2];
			Arrays.fill(t[i], -1);
		}
		while(m--!=0){
			int a = sc.nextInt(), b = sc.nextInt(), x = sc.nextInt();
			t[a][b] = Math.max(t[a][b], x);
		}
		int res = 0;
		for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){
			t[i][j] = Math.max(t[i][j], Math.max(t[i-1][j]-1, t[i-1][j-1]-1));
			res+=t[i][j]>=0?1:0;
		}
		System.out.println(res);
	}

	public static void main(String[] args) {
		new AOJ0574().run();
	}
}