aoj 0574 Nails

• 概要

日本語の問題なので省略させていただきます。

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

• 解法

各点にたいして配列を準備する

h[5000][5000]

しかし5000*5000とか余裕で配列足りないので

h[12512502]

と一つでくくる(このへんの大きさは他の方のソースを参考にささせていただいた)

入力で与えられた三角形の頂点に、入力された三角形の高さXi+1を入れる。

h[f(y,x)]=max(h[f(y-1,x)]-1,h[f(y-1,x-1)])

最終的に上のような形で高さを引き継いでいき、

引き継ぐ途中で初期化した値ではないところがあったらその釘は使うので数える。

各々一回しか頂点は見ないので被っているところも問題なく数えることができます。

#include<cstdio>
#include<algorithm>
#define f(i,j) (i+1)*(i+2)/2+j

using namespace std;

int kyuri[12512502];

int main()
{
	int n,m,y,x,k,cnt=0;

	scanf("%d%d",&n,&m);
	
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&y,&x,&k);
		kyuri[f(y,x)]=k+1;
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			kyuri[f(i,j)]=max(max(kyuri[f(i,j)],kyuri[f(i-1,j)]-1),kyuri[f(i-1,j-1)]-1);
			if(kyuri[f(i,j)]!=0)cnt++;
		}
	}

	printf("%d\n",cnt);
	return 0;
}