背包问题

1. 先循环物体，再循环体积，再循环决策

区间dp

1. 一段一段区间
2. 由包含关系转换而来
3. 一般需要枚举区间长度
4. 可能需要进行左右区间合并
5. 类似于这样的转移 ( f[i][j]=(f[i+1][j],f[i][j-1]) );

for(int len=2;l<=n;++l)
{
    for(int i=1,j;(j=i+len-1)<=n;i++)
    {

    }
}

for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if (len == 1) f[l][r] = 1;
            else
            {
                f[l][r] = inf;
                if (check(l, r)) f[l][r] = min(f[l][r], f[l + 1][r - 1]);
                for (int k = l; k <= r; k++)
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
            }
        }

状态压缩

    for(int s = 0;s<=mx;s++)
    {
        if(s&1)
        {
            for(int i=0;i<21;i++)
            {
                if((1<<i)&s)
                {
                    for(int j=0;j<21;j++)
                    {
                        if(edge[i+1][j+1])
                        if(i!=j && ((1<<j)&s) )
                        dp[s][i] += dp[s^(1<<i)][j];
                    }
                }
            }
        }
    }    

二进制枚举

for(int x=0;x<(1<<n);++x)
{
    for(int i=0;i<n;i++)//遍历x的每一位
    {
        if((x>>i)&1)
        {
            //      
        }
    }
    //
}

三进制枚举

for(int x=0;x<(1<<n);x++)
{
    for(int y=x;;y=(y-1)&x){
        for(int i=0;i<n;i++)
        {
            if((x>>i)&1){
                //
            }
            if((y>>i)&1){
                //
            }
        }
        if(y==0)break;
    }
}
用于枚举集合的一个子集和这个子集的一个子集

树形dp

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n;
int h[N],ne[N*2],e[N<<1],idx,w[N<<1];
int dp[N];//从1走到i点需要反转多少路
int ans[N];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void dfs(int u,int f){
    for(int i=h[u];~i;i=ne[i]){

        int j=e[i];
        if(j==f)continue;
        dfs(j,u);
        dp[u]+=dp[j]+w[i];  
    }
}
void dfs_up(int u,int f){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f)continue;
        dp[j]=dp[u]+(w[i]?-1:1);
        dfs_up(j,u);
    }
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n;
    int x,y;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y,0);
        add(y,x,1);
    }
    dfs(1,-1);
    dfs_up(1,-1);
    return 0;
}