poj 1609 Tiling Up Blocks dp入门之记忆化搜索
发布时间：2020-12-13 20:12:41 所属栏目：PHP教程 来源：网络整理
导读：题意： 给n个2元组（a,b）,要在其中找最长的序列，使得对序列中的任意ij，有ai=aj且bi=bj。 分析： 设dp[a][b]代表以（a,b）结尾的最长序列长度，记忆化搜索便可。 代码： //poj 1609//sep9#include iostreamusing namespace std;const int max_p=128;int n;
|
题意： 给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,sizeof(num));
memset(dp,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,ans=0;
for(i=1;i<=max_l;++i)
for(j=1;j<=max_m;++j)
if(num[i][j])
ans=max(ans,j));
printf("%d
",ans);
}
return 0;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |