样例就没过,看了题解,感觉自己的思路也没有问题啊 加上调试后,居然有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;
}