今天主要做了树形DP，线性DP和区间DP三大DP类型，以及如何考虑一道DP题的做法。下面简单普及一下各类DP的思考模式和模版，以及如何判断一道题是哪种DP类型：{

1线性DP:{最常见的DP类型，主要是考虑当前位置和过去位置的一个状态贡献，一般只要能想到前面的状态是如何影响后面的状态就能做出来

}

2树形DP:{

1.思考形式：个人认为主要是在普通DP的模式上添加了树上的D/BFS，需要留下节点的信息

2.DFS模版：

void dfs(int u,int fa){    
       memset(dp,0,sizeof(dp));
       for(int v：tree[u]){
              if(v==fa) continue；//避免死循环
              dfs(v,u);
              if(满足条件）//统计答案
}
}

}

   3区间DP:{

1. 思考形式：需要对某个区间进行分割或合并，且数据范围在0到5000左右就基本离不开区间DP，主要是记录区间内的信息

2. 模版：

for(int len=1;len<=n;len++){//枚举区间长度
   for(int i=1;i+len-1<=n;i++){//枚举起点和终点
      int j=i+len-1;
       ......
      for(int k=i;k<=j;k++){//遍历区间
         ......
}
}
}

4计数DP（计数DP和线性DP都没有固定模版）{

1. 思考形式：如果需要你统计个数之和或计算合法个数，且数据范围适宜就可能要用，主要记录满足条件的信息

}

}

今日例题：{

**      1 **Mortal Kombat Tower{

1. 题意：一组数据，你和你朋友可轮流来打，一人最多打两下，朋友如果遇到为1数据时需跳过，求跳过次数最大值

2.构思(非正解，但是也能过)：每次都选择打两个，如果朋友打的第二个是1，那么减去这一次的，换我来

}

核心代码：

   for(int i=1;i<n;){
           if(mon[i]==0){i++; continue;}
           int j=i;
           while(j<n&&mon[j]==1) j++;//分步计数
           int len=j-i;
           ans+=len/3;//计算这其中朋友可以跳过多少次
           i=j;
        }

     2 k-Tree{

1. 题意：有一棵无限树，每个父节点都会产生k个枝干，且权值逐个加1，求选择一条路径上权值恰好等于n且有路径权值不小于d的方案数

                   2.思路(完全背包)：可以把权值总和恰好等于n看成背包容积，每个商品都有无限个，只是在背包的基础上增加一条判断是否大于d即可

}

DP过程：

for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i-j<0) continue;
            if(j<d){//没有
                dp[i][0]=(dp[i-j][0]+dp[i][0])%M;//不选，和原来保持一致
                dp[i][1]=(dp[i][1]+dp[i-j][1])%M;
            }
            else dp[i][1]=(dp[i-j][1]+dp[i][1]+dp[i-j][0])%M;//选
        }

**3 **Parsa's Humongous Tree{

1. 题意：一棵树上的n个节点都有一个范围在l到r之间的权值，求一种选择权值的方案，使得相邻两节点的权值差的绝对值之和最大

2. 思路：针对于单个的节点求权值和，我们可以设选择的权值为x，因此可以推出公式:|x-c1|+|x-c2|+...+|x-cn|，不难看出这是一个凸函数，因此我们在这个点权值的选择时一定是选两个范围的最大最小值才有可能得出答案，因此我们设状态dp[u][0]为选左端点时各子节点的权值和最大值,dp[u][1]为选右端点时个子节点的权值和最大值，最后双方取最大值

3. 算法：树形DP

}

DP过程：

void dfs(int u,int fa){
      dp[0][0]=dp[0][1]=0;
      for(int v:tree[u]){
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]+=max(dp[v][0]-abs(l[u]-l[v]),dp[v][1]-abs(l[u]-r[v]));
        dp[u][1]+=max(dp[v][0]-abs(r[u]-r[v]),dp[v][1]-abs(r[u]-l[v]));
}
}

**4 **Four Segments{

1. 题意：给定一个数组，要求三个分割点，使得这三个分割点形成的四个区间满足sum(0,i)-sum(i+1,j)+sum(j+1,k)-sum(k+1,n)

2. 思路：我们只要能确定中间的分割点，那么其余两个分割点就不互相影响了，时间复杂度就会相比暴力枚举大幅下降，并找到值最大的区间分割点

}

核心代码（因为是暴力题，这里直接附全部代码）：

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
ll pre[N];
const ll inf=0x3f3f3f3f3f3f3f;
int ansi,ansj,ansk;
ll ansax=-inf;
int main(){
    freopen("fs.in","r",stdin);
    freopen("fs.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pre[i]=pre[i-1]+x;
    }
   for(int j=0;j<=n;j++){//枚举中间分割点
     int ri,rk;
     ll sum=0;
     ll ma=-inf;
      for(int i=0;i<=j;i++){
        ll s=(pre[i]-pre[0])-(pre[j]-pre[i]);//计算前缀和大小
        if(s>ma){//满足条件才更新
             ma=s; 
             ri=i;
        }
      }
     sum+=ma;
     ma=-inf;
      for(int k=j;k<=n;k++){
         ll s=(pre[k]-pre[j])-(pre[n]-pre[k]);
        if(s>ma){
             ma=s; 
             rk=k;
        }
      }
      sum+=ma;
      if(sum>ansax){
        ansax=sum;
        ansi=ri;
        ansj=j;
        ansk=rk;
      }
   } 
   cout<<ansi<<' '<<ansj<<' '<<ansk; 
}

5 Slime（签到题）{

1. 题意：一组数，任意数可以吞掉与其相邻的数并减去这个数的数值，求最终能得到的数的最大值

2. 思路：因为是相邻数的吞并，所以会有n(n+1)/2种组合方式，最多会有n-1个数的符号改变，最少会有一个数的符号改变，因此我们只需要对原数组进行排序，直接加上第一个数的相反数，之后的数全部与自身的相反数取最大值相加，最后加上不小于零的末尾数得答案

}

核心代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
ll sl[N];
int main(){
   freopen("slime.in","r",stdin);
   freopen("slime.out","w",stdout);
   int n;
   cin>>n;
   for(int i=1;i<=n;i++) cin>>sl[i];  
    if(n==1){cout<<sl[1]; return 0;}
    sort(sl+1,sl+n+1);
    ll ans=0;
    ans+=-sl[1];
   for(int i=2;i<n;i++) ans+=max(sl[i],-sl[i]);
   ans+=sl[n];
   cout<<ans;
}

**6 **Recovering BST{

1. 题意：有一组按升序排列好的节点，求其是否能够组成一棵二叉搜索树，且任意相邻节点的最大公约数都大于1，输出YES?NO

           2.思路：可以先假设有一棵二叉搜索树的子树，这棵树要么属于左树集，要么属于右树集，因为二叉搜索树的左节点都严格小于根节点，右节点都严格大于根节点，所以这棵树的根只可能是自己的前方一点和后方一点，因此这题就可以转化成一道树上的区间DP,枚举每个区间的子树，判断其树是否满足上述条件，如果不行果断跳过，可以则记录答案，最后枚举根节点时，如果可以让自己与自己前后两棵子树相连就是答案，输出YES,没找到输出NO

}

#include <bits/stdc++.h> 
using namespace std;
const int N=705;
typedef long long ll;
ll m[N];
bool l[N][N],r[N][N],dp[N][N];
int gcd(int a,int b){
    return (b==0)?a:gcd(b,a%b);
}
int main(){
    freopen("bst.in","r",stdin);
    freopen("bst.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> m[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            dp[i][j]=dp[j][i]=(gcd(m[i],m[j])>1);//判断是否互质
        } 
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){
              bool leftok=(k==i||r[i][k-1]);//当与左邻居能衔接时或未有左子树时
              bool rightok=(k==j||l[k+1][j]);//当与右邻居能衔接时或未有右子树时
              if(!leftok||!rightok) continue;//不能满足的根节点跳过
              if(i>1&&dp[i-1][k]) l[i][j]=true;//此段左子树可以则标记true
              if(j<n&&dp[j+1][k]) r[i][j]=true;//此段右子树可以则标记true
              if((i==1||l[i][j])&&(j==n||r[i][j])) break;//如果已经满足条件了直接退出
            }
        }
    }
    for(int root=1;root<=n;root++){//最终枚举
         bool leftok=(root==1||r[1][root-1]);
         bool rightok=(root==n||l[root+1][n]);
         if(leftok&&rightok){
            cout << "Yes";
            return 0;
         }
    }
    cout << "No";
}