poj 1609 Tiling Up Blocks dp入门之记忆化搜索

题意：

给n个二元组（a,b）,要在其中找最长的序列，使得对序列中的任意i

分析：

设dp[a][b]代表以（a,b）结尾的最长序列长度，记忆化搜索即可。

代码：

//poj 1609
//sep9
#include 
  
   
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("*\n");
			break;
		}
		int max_l=0,max_m=0;
		memset(num,0,sizeof(num));
		memset(dp,0,sizeof(dp));
		for(int i=0;i