PKU 1609 Tiling Up Blocks
http://poj.org/problem?id=1609
上下に左右n,mの突起と窪みを持ったブロックを積み上げる。
与えられたブロックで積み上げることの出来る最大の高さを求めろというような問題。
動的計画法。配列の初期化を忘れて1WA。
O(n^2)なので通るか微妙な気がしましたが、普通に通りました。
int dp[10000]; PI in[10000]; main(){ int n; while(scanf("%d",&n),n){ memset(dp,0,sizeof(dp)); rep(i,n)scanf("%d%d",&in[i].F,&in[i].S); sort(in,in+n); int ans=0; rep(i,n){ rep(j,i) if(in[i].S>=in[j].S){ dp[i]=max(dp[i],dp[j]+1); ans=max(dp[i],ans); } } printf("%d\n",ans+1); } printf("*\n"); }