1609 Tiling Up Blocks

問題概要

長方形をしており、上の辺の左側に突起がl個、中央に突起がm個ある板がある。
板の下の辺には同じ位置に同じ個数だけくぼみがあり、板を並べることができる。

2枚の板の突起の数をl,m,l',m'とすると、l≧l', m≧m'のとき板を並べることができる。

n枚の板の中から何枚かを選んで板を一列に並べるとき、もっとも多く並べられる枚数を求めよ。
l,m≦100, n≦10000とする。

解法

まずはn枚の板をlの小さい順（同じ場合はmの順）に並べる。
すると、lにういては添え字の番号が大きくなるように取るようにすればよくなるので、
mについてだけ考えればよい。

dp[i][j]を板i枚まで見て、最後の突起の数がj個であるような列の長さの最大値とすると、漸化式が立ってDPできる。

ソースコード

int n,dp[10001][101];
pi p[10000];

int main(){
	while(scanf("%d",&n),n){
		rep(i,n)scanf("%d%d",&p[i].first,&p[i].second);
		sort(p,p+n);
		
		rep(i,n+1)rep(j,101)dp[i][j]=0;
		rep(i,n)rep(j,101)
		{
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			if(j<=p[i].second)dp[i+1][p[i].second]=max(dp[i+1][p[i].second],dp[i][j]+1);
		}
		int ans=1;
		rep(j,101)ans=max(ans,dp[n][j]);
		printf("%d\n",ans);
	}
	puts("*");
	return 0;
}