AOJ0057 The Number of Area

AOJ Volume0

問題リンク The Number of Area

  • 解法

ノートに直線を引いて分割してみます。すると、法則が見えてきます。
既に直線がn本あるとき、n+1本目の直線を適切に引くと新たに面はn+1個増えます。
なので
dp[i] : 直線がi本あるときの面の数
dp[i] = dp[i-1] + i
というDPで解けます。

  • ソース
import java.util.Scanner;

//The Number of Area
public class AOJ0057 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a[] = new int[10001];
		a[0] = 1;
		for(int i=1;i<10001;i++)a[i]=a[i-1]+i;
		while(sc.hasNext())System.out.println(a[sc.nextInt()]);
	}
}