Evolution Game DAG 上的DP 有向無環圖的 動态規劃

輸入怪獸數量 n ，以及眼睛的變化範圍 w ，

怪獸1 号 的 角的數量，，，，，n号角的數量  眼睛的數量就是下标，

可以進化，隻能向角大的變

滿足這個w 變化範圍的，怪獸最多可以變化幾次形态

DAG 上的DP，，具體在紫書上有，，，有向無環圖的動态規劃

一個狀态可以到達另一個狀态，，，狀态就是圖中的點，，能到 就是說明有邊，這個題找的是最長的路

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
  
int n,w;
typedef struct
{
    int eye;
    int horn;
}M;
  
M mo[5005];
int vis[5005][5005];
int dp[5005]={0};
bool cmp(M a,M b){
    if(a.horn==b.horn)
        return a.eye<b.eye;
  
    return a.horn<b.horn;
}
  
int DP(int i)
{
    int& ans=dp[i];
  
    if(ans>0) return ans;
  
    ans=1;
  
    for(int j=i;j<=n;j++)
    {
        if(vis[i][j])
        ans=max(ans,DP(j)+1 );
    }
    return ans;
}
  
  
int main()
{
  
    cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        mo[i].eye=i;
        cin>>mo[i].horn;
    }
  
    sort(mo+1,mo+1+n,cmp);
  
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
    {
        if( mo[j].horn>mo[i].horn )
                {
            if(mo[j].eye >= mo[i].eye-w && mo[j].eye<=mo[i].eye+w )
                vis[i][j]=1;
        }
    }
  
  
for(int i=n;i>=1;i--)
    DP(i);
  
  
    int c=0;
    for(int i=1;i<=n;i++)
    c=max(c,dp[i]);
  
  
    cout<<c-1<<endl;
//
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)
//        cout<<vis[i][j]<<"   ";
//        cout<<'\n';
//    }
//
//for(int i=1;i<=n;i++)
//    cout<<dp[i]<<endl;
  
  
    return 0;
}
  
           

如果說不按照 角的數量排序的話 就 找dp 的時候從頭周遊

int DP(int i)
{
    int& ans=dp[i];
  
    if(ans>0) return ans;
  
    ans=1;
  
    for(int j=1;j<=n;j++)
    {
        if(vis[i][j])
        ans=max(ans,DP(j)+1 );
    }
    return ans;
}
  
           

我忍不住要舔一波了，，這個遞歸寫的太好了， 

推出了 狀态轉移方程， dp[i] = max(dp[i]  , dp [ j ] +1 ),  max 裡面的 dp[ i ] 代表已經通路過好多 j  之後的答案，，那個 j 表示的是 新的 j 是否可以改變最大值

這個題不排序就從前面所有的都找，，（紫書的矩形嵌套問題就 沒辦法排序） ，排序之後 的j  就隻能是目前狀态後面的狀态了。

先說排序之後的

那麼 我們  的dp[i] = max(dp[i]  , dp [ j ] +1 )  i  需要   j的狀态已知才能推出i  ， j 又在i  後面，是以 從後往前 DP（i） 就行了

不排序的話就 從前往後還是從後往前 都是無所謂的，因為 每次都要把其他所有狀态都找一遍就行了

int DP(int i)
{
    int& ans=dp[i];
 
    if(ans>0) return ans;
 
    ans=1;
 
    for(int j=1;j<=n;j++)   // 把所有狀态都找一遍
    {
        if(vis[i][j])
        ans=max(ans,DP(j)+1 );
    }
    return ans;
}


for(int i=n;i>=1;i--)  // 1--> n   還是n --->1  無所謂的
    DP(i);