DP经典题目

题意还是比较好懂就是矩形嵌套，不过这个矩阵是m维的，而且嵌套要严格大于。

输入n和m，表示有n个维数为m的超立方体。下面n行每行m个数字，是每个超立方体的信息，即每个维的大小

超立方体的信息可以调整，判断一个超立方体a能不能套住超立方体b是看调整之后能不能

好像（2，6）和（7，3），可以调整为（2,6），（3,7），那么显然（3,7）是能套住（2,6）的

另外能不能套住，还需要每一维都严格大于，好像（2,6），（2,7），由于2相等不能套住

 

其实就是DAG模型，若i能套住j，则g[i][j]=1，然后这个有向图显然是无环的，（要套住必须严格大于，不可能存在互相套住的情况）。相当于求这个DAG上的最长路，dp思想就是  dp[i]=max{ dp[j]+1 };  (i能套住j)  ， 这个dp思想用记忆化搜索很容易实现，详细看代码

另外我们把套住这种关系看做一种大于关系（i能套住j则认为i大于j），那么对超立方体内部信息排序后，还要对所有的超立方排序，得到一个“递增”的序列，再对这个递增的序列求LIS，个人觉得这个方法没有求最长路来得简单和直接，所以代码就不写了

 

后来想了另一种dp思想，就是求出任意两点的最长路，即dp[i][j]表示i到j的最长路，然后找到最大的dp[i][j]就是整个图的最长路

dp过程仿照floyd写3个循环。如果i能套住k，k能套住j，那么dp[i][j]=max( dp[i][j] , dp[i][k]+dp[k][j])

这个dp思想其实很好理解，看起来也没什么问题，但是一直wa，几乎想放弃了，然后出了随机数据来测才找到bug

算是逻辑不够严谨，这和整个图的特殊情况也有关系，所以初始化要处理好

1.整个图可以是独立的，根本没有边，也就是说所有超立方体都不能互相嵌套，整个图的最长路是0，顶点个数是1

2.整个图的最长路为1，即只有两两嵌套的情况，那个顶点个数是2。

这个两个特殊情况都有一个共同点，就是整个dp过程都没办法去更新dp[i][j]，（因为都不可能找到一个k插进去）

所以更新最大值的语句不能放在  if(i,k && k,j)循环内部，而应该放在3个for里面，即有没有更新dp[i][j]都好，都要拿dp[i][j]更新max

具体看代码

 

 

记忆化搜索AC代码

#include 
     
      #include 
      
       #include 
       
        #define N 35#define M 15using namespace std;int dp[N],p[N],g[N][N];int n,m;struct box{    int a[M];}b[N];int ans,x;int can_nest(int i , int j)  //判断i能不能套住j{    for(int k=0; k
        
         dp[i])            {                dp[i]=dp[j]+1;                p[i]=j;            }        }    if(dp[i]>ans)    {        ans=dp[i];        x=i;    }    return ;}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=1; i<=n; i++)            for(int j=0; j
         
          =0; i--)   //注意路径中最后一个数字不能有空格            if(i>0) printf("%d ",s[i]);            else    printf("%d",s[i]);        printf("\n");    }    return 0;}
         
        
       
      
     

 

 

在DAG上仿照floyd的dp，我找遍了所有的解题报告，没有人用这个方法的，算是原创吧……

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 35#define M 15struct box{    int a[M];}b[N];int n,m;int dp[N][N],p[N][N];int can_nest(int i , int j)  //i盒子能套住j盒子{    for(int k=0; k
        
          dp[i][j])                    {                        dp[i][j]=dp[i][k]+dp[k][j];                        p[i][j]=p[i][k];                    }                }                //这个更新最大值不能放在                //if(can_nest(i,k) && can_nest(k,j))内部                //因为可能整个图没有办法找到一个k去更新ij                //也就是整个图的最长路是1或0，只有两个点或孤立，即一个矩形套住另一个或不能互相嵌套                if(dp[i][j]>max)                { max=dp[i][j]; x=i; y=j;}            }    max++;  //最长路+1才是顶点个数    printf("%d\n",max);        //用栈储存路径，当然也可以递归打印    int stack[N],top;     top=0;    stack[top]=x;    while(x!=y)    {        x=p[x][y];        stack[++top]=x;    }    while(top>=0)    {        if(top) printf("%d ",stack[top]);        else    printf("%d",stack[top]);        top--;    }    printf("\n");}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=1; i<=n; i++)            for(int j=0; j