题目链接：点击打开链接

DAG（有向无环图）上的最长路+打印路径建图很简单，对于两点 a b, 能够由a到b的条件是w[a] s[b] 注意是有向图。设dp[i] 为以i为起点的最长路的长度，dp[i]= max(dp[i],dp[j]+1) 枚举j (j是和i相连的点)

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #define maxn 1010 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair
                
                  #define ull unsigned long long using namespace std; int p,w[maxn],s[maxn],dp[maxn]; bool ma[maxn][maxn]; void build() { memset(ma,0,sizeof(ma)); for(int i=1;i
                 





                  s[j]) ma[i][j]=1; else if(w[j]
                  
                   s[i]) ma[j][i]=1; } } } int dfs(int x) { int& ans=dp[x]; if(ans>0) return ans; ans=1; for(int i=1;i

Uva 10131-Is Bigger Smarter?（DP）

题目链接：点击打开链接