poj 1609 Tiling Up Blocks dp入門之記憶化搜索
來源：程序員人生 發(fā)布時間：2015-01-23 08:17:12 閱讀次數(shù)：3964次
題意：
給n個2元組（a,b）,要在其中找最長的序列，使得對序列中的任意i<j，有ai<=aj且bi<=bj。
分析：
設(shè)dp[a][b]代表以（a,b）結(jié)尾的最長序列長度，記憶化搜索便可。
代碼：
//poj 1609
//sep9
#include <iostream>
using namespace std;
const int max_p=128;
int n;
int num[max_p][max_p];
int dp[max_p][max_p];
int search(int x,int y)
{
if(dp[x][y])
return dp[x][y];
int i,j,maxx=0;
for(i=1;i<=x;++i)
for(j=1;j<=y;++j)
if(!(i==x&&j==y))
if(num[i][j])
maxx=max(maxx,search(i,j));
return dp[x][y]=maxx+num[x][y];
}
int main()
{
while(scanf("%d",&n)==1){
if(n==0){
printf("*
");
break;
}
int max_l=0,max_m=0;
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;++i){
int a,b;
scanf("%d%d",&a,&b);
++num[a][b];
max_l=max(max_l,a);
max_m=max(max_m,b);
}
int i,j,ans=0;
for(i=1;i<=max_l;++i)
for(j=1;j<=max_m;++j)
if(num[i][j])
ans=max(ans,search(i,j));
printf("%d
",ans);
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
