非常疑惑的地方
查看原帖
非常疑惑的地方
182053
Crystal_Clear楼主2024/8/8 15:48

样例就没过,看了题解,感觉自己的思路也没有问题啊 加上调试后,居然有x=4的地方,就是这里不知道原理

//递归 
//记忆化搜索 
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 1<<30
using namespace std;
int n,x1[31],y1[31],z1[31],i,j,k,a[91][91]={0},x[91],y[91],z[91],maxl,mem[91],cnt=0;
//a[i][j]表示第i个可以放在第j个下面 也就是第i个比第j个大 
int dp(int x)	//返回以x号方块为顶的最长序列 
{
	if(mem[x]>=0)
	{
		printf("第%d次调用dp函数,此时x的值是%d,返回%d\n",++cnt,x,mem[x]);
		return mem[x];
	}
	for(j=1;j<=n*3;j++)
	{
		if(a[j][x] && dp(j)>mem[x])
		{
			mem[x]=dp(j);
			printf("mem[%d]的值变更为%d\n",x,mem[x]);
		}
	}
	if(mem[x]==-1)
	{
        printf("第%d次调用dp函数,此时x的值是%d,返回%d\n",++cnt,x,z[x]);
		return z[x];
	} 
	mem[x]+=z[x];
	printf("mem[%d]的值变更为%d\n",x,mem[x]);
	printf("第%d次调用dp函数,此时x的值是%d,返回%d\n",++cnt,x,mem[x]);
	return mem[x];
} 
int main()
{
	memset(mem,-1,sizeof(mem));
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x1[i]>>y1[i]>>z1[i];
		x[i]=x1[i];y[i]=y1[i];z[i]=z1[i];
		x[i*2]=x1[i];y[i*2]=z1[i];z[i*2]=y1[i];
		x[i*3]=y1[i];y[i*3]=z1[i];z[i*3]=x1[i];
	}
	//构建矩阵
	for(i=1;i<=n*3;i++)
	{
		for(j=1;j<=n*3;j++)
		{
			if((x[i]>x[j] && y[i]>y[j]) || (x[i]>y[j] && y[i]>x[j]))
			{
	          a[i][j]=1;
			}
		}
	} 
	maxl=0;
	/**/
	for(i=1;i<=n*3;i++)
	{
		if(dp(i)>maxl)
		{
			maxl=dp(i);
		}
		//cout<<dp(i)<<endl;
	}
	//cout<<maxl;
	return 0;
}
2024/8/8 15:48
加载中...