poj 1609 Tiling Up Blocks dp入门之记忆化搜索
来源：程序员人生 发布时间：2015-01-23 08:17:12 阅读次数：3801次
题意：
给n个2元组（a,b）,要在其中找最长的序列，使得对序列中的任意i<j，有ai<=aj且bi<=bj。
分析：
设dp[a][b]代表以（a,b）结尾的最长序列长度，记忆化搜索便可。
代码：
//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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
