Blog Detail

C20250045's blog
关于树型DP和状压DP的一些知识
C20250045 LV 4 @ 2023-5-30 21:41:28

技巧	示例	代码实现
去掉最后一位	(101101->10110)	x >> 1
在最后加一个0	(101101->1011010)	x << 1
在最后加一个1	(101101->1011011)	x << 1 + 1
把最后一位变成1	(101100->101101)	x or 1
把最后一位变成0	(101101->101100)	x or 1 - 1
最后一位取反	(101101->101100)	x ^ 1
把右数第k位变成1	(101001->101101,k=3)	x or (1 << (k - 1))
把右数第k位变成0	(101101->101001,k=3)	x and ~(1 << (k - 1))
右数第k位取反	(101001->101101,k=3)	x ^ (1 << (k - 1))
取末k位	(1101101->1101,k=5)	x and (1 << k - 1)
取右数第k位	(1101101->1,k=4)	x >> (k - 1) and 1
把末k位变成1	(101001->101111,k=4)	x or (1 << k - 1)
末k位取反	(101001->100110,k=4)	x ^ (1 << k - 1)
把右起第一个0变成1	(100101111->100111111)	x or (x + 1)
把右起第一个1变成0	(11011000->11010000)	x and (x − 1)
把右边连续的0变成1	(11011000->11011111)	x or (x - 1)
把右边连续的1变成0	(100101111->100100000)	x and (x + 1)
取右边连续的1	(100101111->1111)	(x ^ (x + 1)) >> 1

状态压缩DP其实是一种暴力的算法，因为它需要遍历每个状态，而每个状态是多个事件的集合，也就是以集合为状态，一个集合就是一个状态。集合问题一般是指数复杂度的NP问题，所以状态压缩DP的复杂度仍然是指数的，只能用于小规模问题的求解。

为了方便地同时表示一个状态的多个事件，状态一般用二进制数来表示。一个数就能表示一个状态，通常一个状态数据就是一个一串0和1组成的二进制数，每一位二进制数只有两种状态，比如说硬币的正反两面，10枚硬币的结果就可以用10位二进制数完全表示出来，每一个10位二进制数就表示了其中一种结果。

1、什么是树型动态规划

树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：

叶－>根：在回溯的时候从叶子节点往上更新信息

根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。

不管是从叶－>根还是从根 - >叶，两者都是根据需要采用，没有好坏高低之分。

2、树真的是一种特别特别优美的结构！

用来做动态规划也简直是锦上添花再美不过的事，因为树本身至少就有“子结构”性质（树和子树）；本身就具有递归性。所以在树上DP其实是其所当然的事，相比线性动态规划来讲，转移方程更直观，更易理解。

3、难点

和线性动态规划相比，树形DP往往是要利用递归+记忆化搜索。

细节多，较为复杂的树形DP，从子树，从父亲，从兄弟……一些小的要处理的地方，脑子不清晰的时候做起来颇为恶心

状态表示和转移方程，也是真正难的地方。做到后面，树形DP的老套路都也就那么多，难的还是怎么能想出转移方程，各种DP做到最后都是这样！

选择节点类

$f[i][0]=f[j][1]$

$f[i][1]=max/min(f[j][0],f[j][1])$

树形背包类

$f[v][k]=f[u][k]+val$

$f[u][k]=max(f[u][k],f[v][k−1])$

换根DP，又叫二次扫描，是树形DP的一种。

其相比于一般的树形DP具有以下特点：

以树上的不同点作为根，其解不同。

故为求解答案，不能单求某点的信息，需要求解每个节点的信息。

故无法通过一次搜索完成答案的求解，因为一次搜索只能得到一个节点的答案。

难度也就要比一般的树形DP高一点。

树型DP求直径

//C++代码
//采用链式前向星存图
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
const int N=5e5+100;
struct edge{
int u;
int v;
int w;
int next;
}e[2*N];

int head[N],cnt=0;
void Insert(int u,int v,int w){
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}

int vis[N];
int  res=INT_MIN;

int d[N],f[N];
void dfs(int u){
    vis[u]=1;
   for(int i=head[u];i>=0;i=e[i].next){
    int v=e[i].v;
    int w=e[i].w;
    if(!vis[v]){
      dfs(v);
      f[u]=max(max(f[u],d[u]),max(d[v]+w,d[u]+d[v]+w));
      d[u]=max(max(d[u],w),d[v]+w);
    }
   }
}
int main(){
    memset(head,-1,sizeof(head));
int n;
scanf("%d",&n);
int u,v,w;
for(int i=1;i<=n-1;i++){
    scanf("%d%d%d",&u,&v,&w);
    Insert(u,v,w);
    Insert(v,u,w);
}

dfs(1);
for(int i=1;i<=n;i++) res=max(res,f[i]);
printf("%d\n",res);
return 0;
}

void dfs(int  x,int pa){
    for(int i=head[x];i;i=edge[i].nxt){
        int  y=edge[i].to;
        if(pa==y) continue ; 
        dfs(y,x);
        maxlen=max(maxlen,dp[x]+dp[y]+edge[i].val);    
        dp[x]=max(dp[x],dp[y]+edge[i].val);
    }
}

P1352 没有上司的舞会

某大学有 $n$ 个职员，编号为 $1 \sim N$ 。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $a_i$ ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

#include <algorithm>
#include <cstdio>
using namespace std;

struct edge {
  int v, next;
} e[6005];

int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];

void addedge(int u, int v) {  // 建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  // 转移方程
  }
  return;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &f[i][1]);
  for (int i = 1; i < n; i++) {
    int l, k;
    scanf("%d%d", &l, &k);
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      printf("%d", max(f[i][1], f[i][0]));
      return 0;
    }
}

HDU 2196 Computer

给定一棵有边权的树，求每个点能到达的最远距离。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=10005;
struct node
{
  int v,w;
  node(){}
  node(int a,int b)
   {v=a;w=b;}
};
vector<node> e[maxn];
int n,dp[maxn][3];
void dfs1(int s,int fa);
void dfs2(int s,int fa);
int main()
{
   int i,j,a,b;
   while(~scanf("%d",&n))
   {
      for(i=0;i<maxn;i++) e[i].clear();
      fill(dp[0],dp[0]+maxn*3,0);
      for(i=2;i<=n;i++)
      {
        scanf("%d%d",&a,&b);
        e[i].push_back(node(a,b));
        e[a].push_back(node(i,b));
      }
      dfs1(1,-1);
      dfs2(1,-1);
      for(i=1;i<=n;i++) printf("%d\n",max(dp[i][0],dp[i][2]));
   }
  system("pause");
  return 0;
}
void dfs1(int s,int fa)  //子树方向的最大距离和次大距离
{
  int i,v,w;
  for(i=0;i<e[s].size();i++)
   {
     v=e[s][i].v;
     if(v==fa) continue;
     dfs1(v,s);
     w=dp[v][0]+e[s][i].w;
     if(w>=dp[s][0])
      {
        dp[s][1]=dp[s][0];
        dp[s][0]=w;
      }
     else if(w>dp[s][1]) dp[s][1]=w;
   }
}
void dfs2(int s,int fa)  //父亲方向的最大距离
{
  int i,v,w;
  for(i=0;i<e[s].size();i++)
  {
    v=e[s][i].v;w=e[s][i].w;
    if(v==fa) continue;
    if(dp[s][0]==dp[v][0]+w) dp[v][2]=max(dp[s][1],dp[s][2])+w;
    else dp[v][2]=max(dp[s][0],dp[s][2])+w;
    dfs2(v,s);
  }
}

POJ 1463 Strategic game

告诉你一棵树，如果一个节点放一个士兵的话，那么这么士兵可以看到这个节点以及和这个节点直接连接的节点，然后问你最少要放多少个士兵可以使得所有的节点都能被看到。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<algorithm>
using namespace std;
const int maxn=1502;
int d[maxn][2];
int gra[maxn][maxn];
int flag[maxn];
int n;
void dp(int cur){
    flag[cur]=1;
    if(d[cur][0]>=0||d[cur][1]>=0){
        return;
    }
    int leaf=1;
    for(int i=0;i<n;i++){
        if(gra[cur][i]&&flag[i]!=1){
            leaf=0;
            dp(i);
            if(d[cur][0]==-1)d[cur][0]=0;
            if(d[cur][1]==-1)d[cur][1]=0;
            d[cur][0]+=d[i][1];
            d[cur][1]+=min(d[i][0],d[i][1]);
        }
    }
    d[cur][1]++; 
    if(leaf==1){
        d[cur][0]=0;d[cur][1]=1;
    }
}
int main(void){
    while(scanf("%d",&n)){
        memset(flag,0,sizeof(flag));
        memset(gra,0,sizeof(gra));
        memset(d,-1,sizeof(d));
        int x,cnt;
        int num=n;
        while(num--){
            scanf("%d:(%d)",&x,&cnt);
            while(cnt--){
                int tem;
                scanf("%d",&tem);
                gra[x][tem]=1;
                gra[tem][x]=1;
            }
        }
        dp(x);
        int ans=min(d[x][0],d[x][1]);
        cout<<ans<<endl;
    }
    return 0;
}

P2014 CTSC1997 选课

现在有 $n$ 门课程，第 $i$ 门课程的学分为 $a_i$ ，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

一位学生要学习 $m$ 门课程，求其能获得的最多学分数。

$n,m \leq 300$

$f(u,i,j)=\max_{v,k \leq j,k \leq \textit{siz_v}} f(u,i-1,j-k)+f(v,s_v,k)$

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];

int dfs(int u) {
  int p = 1;
  f[u][1] = s[u];
  for (auto v : e[u]) {
    int siz = dfs(v);
    // 注意下面两重循环的上界和下界
    // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
    for (int i = min(p, m + 1); i; i--)
      for (int j = 1; j <= siz && i + j <= m + 1; j++)
        f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
    p += siz;
  }
  return p;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int k;
    scanf("%d%d", &k, &s[i]);
    e[k].push_back(i);
  }
  dfs(0);
  printf("%d", f[0][m + 1]);
  return 0;
}

「SDOI2017」苹果树

树上求背包最大收益，每个物品的体积都是 $1$ ，同一个物品可以取 $a_i$ 次，并且取儿子必须取父亲，除此之外，我们还可以免费取一条最长链

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=4*1e4+10;const int K=5*1e5+10;const int NK=6*1e7+10;
inline void clear(vector <int>& ve){vector <int> emp;swap(emp,ve);}//高速清空函数 
vector <int> v[N];int w[N];int a[N];int n;int res;int ctt;int k;
int dfn1[N];int dfn2[N];int df1;int df2;int siz[N];int line[N];
int dp1[NK];int dp2[NK];bool lf[N];int nfd1[N];int nfd2[N];int T;
int h;int fa[N];int q1[2*K];int q2[2*K];int hed=1;int til=0;
inline void dypr(int* dfn,int* dp)//dp的函数 
{
    for(int i=1;i<=ctt;i++)
    {
        int v=dfn[i];hed=1;til=1;q1[til]=q2[til]=0;//手动inline了全部的deque操作，凑合着看吧 
        for(int j=1;j<=k;j++)
        {
            hed+=(q1[hed]<j-a[v])?1:0;int val=dp[(i-1)*(k+1)+j]-j*w[v];
            dp[i*(k+1)+j]=max(q2[hed]+j*w[v],dp[(i-siz[v])*(k+1)+j]);//单调队列优化转移 
            while(hed<=til&&q2[til]<=val){til--;}q1[++til]=j;q2[til]=val;
        }
    }
}
inline void clear_all()//清空函数 
{
    for(int i=0;i<=ctt;i++){clear(v[i]);lf[i]=line[i]=siz[i]=0;}
    for(int i=0;i<=(ctt+1)*(k+1);i++){dp1[i]=dp2[i]=0;}
    df1=df2=res=ctt=0;h=0;
}
void dfs1(int x)//正着dfs，原谅我毒瘤压行 
{
    siz[x]=1;
    for(int i=0;i<v[x].size();i++)
    {dfs1(v[x][i]);siz[x]+=siz[v[x][i]];}dfn1[++df1]=x;nfd1[x]=df1;
}
void dfs2(int x)//reverse后dfs 
{
    for(int i=v[x].size()-1;i>=0;i--)
    {line[v[x][i]]=line[x]+w[v[x][i]];dfs2(v[x][i]);}
    dfn2[++df2]=x;nfd2[x]=df2;
}
inline void solve()
{
    scanf("%d%d",&n,&k);ctt=n;
    for(int i=1;i<=n;i++){scanf("%d%d%d",&fa[i],&a[i],&w[i]);lf[fa[i]]=true;}
    for(int i=1;i<=n;i++)//加边和拆点 
    {
        v[fa[i]].push_back(i);
    	if(a[i]>1){a[++ctt]=a[i]-1;a[i]=1;w[ctt]=w[i];v[i].push_back(ctt);}
    }line[1]=w[1];dfs1(1);dfs2(1);dypr(dfn1,dp1);dypr(dfn2,dp2);//dfs和dp 
    for(int i=1;i<=n;i++)//枚举叶子更新答案 
    {
        if(lf[i])continue;
        for(int j=0;j<=k;j++)
        {res=max(res,dp1[(nfd1[i]-1)*(k+1)+j]+line[i]+dp2[(nfd2[i]-siz[i])*(k+1)+(k-j)]);}
    }printf("%d\n",res);//然后靠信仰卡常吧 
}
int main()
{scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear_all();}return 0;}//拜拜程序~

[POI2008]STA-Station

给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

#include <bits/stdc++.h>
using namespace std;

int head[1000010 << 1], tot;
long long n, sz[1000010], dep[1000010];
long long f[1000010];

struct node {
  int to, next;
} e[1000010 << 1];

void add(int u, int v) {  // 建图
  e[++tot] = {v, head[u]};
  head[u] = tot;
}

void dfs(int u, int fa) {  // 预处理dfs
  sz[u] = 1;
  dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

void get_ans(int u, int fa) {  // 第二次dfs换根dp
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      f[v] = f[u] - sz[v] * 2 + n;
      get_ans(v, u);
    }
  }
}

int main() {
  scanf("%lld", &n);
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  dfs(1, 1);
  for (int i = 1; i <= n; i++) f[1] += dep[i];
  get_ans(1, 1);
  long long int ans = -1;
  int id;
  for (int i = 1; i <= n; i++) {  // 统计答案
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  printf("%d\n", id);
  return 0;
}

POJ 3585 Accumulation Degree

给定一棵树。

· 树的每个边都具有正边权，代表边的容量。

· 树中度为1的点被命名为出海口。

· 每个边的流量不能超过容量。

$A(x)$ 是将点 $x$ 视作一个无线喷水机，表示点 $x$ 可以流到其他（如果他也是出海口，则排除他）出海口的最大流量。

你的任务找一个点，使这个最佳最大流量，输出这个值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
const int N=200001;
int t,n,u,v,w,head[N],numE=0,d[N],du[N],dp[N],ans,s;
struct Edge{
    int next,to,dis;
}e[2*N];
void addEdge(int from,int to,int dis){
    e[++numE].next=head[from];
    e[numE].to=to;
    e[numE].dis=dis;
    head[from]=numE;
}
int dfs_(int x,int l){
    int p=0;d[x]=0;
    for(int j=head[x];j;j=e[j].next){
        int v=e[j].to;
        if(v==l)continue;
        p+=min(e[j].dis,dfs_(v,x));
    }
    if(du[x]!=1)return d[x]=p; 
    else return e[head[x]].dis;
}
void dfs(int x,int l){
    for(int j=head[x];j;j=e[j].next){
        int v=e[j].to;
        if(v==l)continue;
        if(du[x]==1)dp[v]=e[j].dis+d[v];
        else dp[v]=d[v]+min(e[j].dis,dp[x]-min(e[j].dis,d[v]));
        ans=max(ans,dp[v]);
        dfs(v,x);
    }
}
int main() {
    scanf("%d",&t);
    while(t--){
        memset(head,0,sizeof(head));
        memset(d,0,sizeof(d));
        memset(dp,0,sizeof(dp));
        memset(du,0,sizeof(du));
        numE=0;ans=0;
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            addEdge(u,v,w);addEdge(v,u,w);
            du[u]++;du[v]++;
        }
        dp[2]=dfs_(1,-1);
        dfs(1,-1);
        printf("%d\n",max(dp[1],ans));
    }
    return 0;
}

[USACO10MAR]Great Cow Gathering G

$Bessie$ 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

每个奶牛居住在 $N$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $A_i$ 和 $B_i$ ，长度为 $L_i$ 。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。

在选择集会的地点的时候， $Bessie$ 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$ ，那么总路程就是 $C_i\times 20$ ）。帮助 $Bessie$ 找出最方便的地点来举行大集会。

#include<bits/stdc++.h>
#define bl(i,a) for(long long i=head[a];i;i=nxt[i])
using namespace std;
const int N=2e6+3;

long long nxt[N],edge[N],head[N],dis[N],tot,n,c[N],sum,ans=1e17;
void add(int x,int y,int w){
	nxt[++tot]=head[x];
	head[x]=tot;
	edge[tot]=y;
	dis[tot]=w;
}

long long siz[N],f[N];
void getsiz(int me,int dad){
	siz[me]=c[me];
	bl(i,me){
		int v=edge[i];
		if(v==dad)continue;
		getsiz(v,me);
		siz[me]+=siz[v];
		f[me]=f[me]+f[v]+siz[v]*dis[i];
	}
}

long long d[N];
void dp(int me,int dad){
	bl(i,me){
		int v=edge[i];
		if(v==dad)continue;
		d[v]=1ll*d[me]-siz[v]*dis[i]+(sum-siz[v])*dis[i];
		ans=min(d[v],ans);
		dp(v,me);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];sum+=c[i];
	}
	for(int i=1,l,r,w;i<n;i++){
		cin>>l>>r>>w;
		add(l,r,w);add(r,l,w);
	}
	getsiz(1,0);
	d[1]=f[1];
	dp(1,0);
	cout<<ans;
}

「SCOI2005」互不侵犯

在 $N\times N$ 的棋盘里面放 $K$ 个国王（ $1 \leq N \leq 9, 1 \leq K \leq N \times N$ ），使他们互不攻击，共有多少种摆放方案。

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;

void dfs(int x, int num, int cur) {
  if (cur >= n) {  // 有新的合法状态
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // cur位置不放国王
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // cur位置放国王，与它相邻的位置不能再放国王
}

bool compatible(int j, int x) {
  if (sit[j] & sit[x]) return false;
  if ((sit[j] << 1) & sit[x]) return false;
  if (sit[j] & (sit[x] << 1)) return false;
  return true;
}

int main() {
  cin >> n >> k;
  dfs(0, 0, 0);  // 先预处理一行的所有合法状态
  for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
      for (int x = 1; x <= cnt; x++) {
        if (!compatible(j, x)) continue;  // 排除不合法转移
        for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
      }
  long long ans = 0;
  for (int i = 1; i <= cnt; i++) ans += f[n][i][k];  // 累加答案
  cout << ans << endl;
  return 0;
}

「NOI2001」炮兵阵地

给你一张有 $N \times M$ 的平原和山地的图，只能在平原上放置炮兵，炮兵的攻击范围为 $5 \times 5$ 的十字，求最多能放多少个炮兵？

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=100+5;
const int maxm=(1<<10);

int n,m,top,state[maxm],dp[2][maxm][maxm];
int cur[maxm],ans,w=1;
char c;

bool ok(int x){
    if(x&(x<<1)) return false;
    if(x&(x<<2)) return false;
    return true;
}

void init(){
    for(int i=0;i<(1<<m);i++)
    if(ok(i)) state[++top]=i;
}

bool fit(int x,int k){
    if(x&cur[k]) return false;
    return true;
}

bool pd(int x,int y){
    if(state[x]&state[y]) return false;
    return true;
}

int count(int x){
    int ret=0;
    while(x){
        ret++;
        x&=x-1;
    }
    return ret;
}

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        cur[i]=0;
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='H') cur[i]+=(1<<m-j);
        }
    }
    init();
    for(int i=1;i<=top;i++)
    if(fit(state[i],1)) dp[1][i][0]=count(state[i]);
    
    for(int i=1;i<=top;i++){
        if(!fit(state[i],2)) continue;
        int tot=count(state[i]);
        for(int k=1;k<=top;k++){
            if(!fit(state[k],1)) continue;
            if(!pd(i,k)) continue;
            dp[0][i][k]=max(dp[0][i][k],dp[1][k][0]+tot);
        }
    }
    for(int i=3;i<=n;i++,w^=1)
    for(int j=1;j<=top;j++){
        if(!fit(state[j],i)) continue;
        int tot=count(state[j]);
        for(int k=1;k<=top;k++){
            if(!fit(state[k],i-1)) continue;
            if(!pd(j,k)) continue;
            for(int t=1;t<=top;t++){
                if(!fit(state[t],i-2)) continue;
                if(!pd(j,t)||!pd(t,k)) continue;
                dp[w][j][k]=max(dp[w][j][k],dp[w^1][k][t]+tot);
            }
        }
    }
    
    for(int i=1;i<=top;i++){
        if(!fit(state[i],n)) continue;
        for(int j=1;j<=top;j++){
            if(!fit(state[j],n-1)) continue;
            if(!pd(i,j)) continue;
            ans=max(ans,dp[w^1][i][j]);
        }
    }
    cout<<ans;
    return 0;
}

「USACO06NOV」玉米田 Corn Fields

农场主John新买了一块长方形的新牧场，这块牧场被划分成 $M$ 行 $N$ 列 $(1 \leq M \leq 12 ; 1 \leq N \leq 12)$ ，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？

#include<cstdio>
using namespace std;
const int P = 1e8;
long long f[14][4400];
int sta[14][4400],n,m,a[14][14];

void dfs(int u,int x,int s)\\预处理状态
{
	if (x > m)
	{
		sta[u][++sta[u][0]] = s;
		return;
	}
	dfs(u,x + 1,s);
	if (a[u][x]) dfs(u,x + 2,s | (1 << x - 1));
}
int main()
{
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d",&a[i][j]);
	for (int i = 1; i <= n; i++)
		dfs(i,1,0);
	for (int i = 1; i <= sta[1][0]; i++) f[1][i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= sta[i][0]; j++)
			for (int k = 1; k <= sta[i - 1][0]; k++)
			{
				if (sta[i][j] & sta[i - 1][k]) continue;\\排除不可能的情况
				f[i][j] = (f[i][j] + f[i - 1][k]) % P;
			}
	long long ans = 0;
	for (int i = 1; i <= sta[n][0]; i++) ans = (ans + f[n][i]) % P;
	printf("%lld\n",ans);
}

###「AHOI2009」中国象棋

这次小可可想解决的难题和中国象棋有关，在一个 $n$ 行 $m$ 列的棋盘上，让你放若干个炮（可以是 $0$ 个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstring>
#define mod 9999973
#define int long long
#define R register
using namespace std;
inline  void in(int &x)
{
	int f=1;x=0;char s=getchar();
	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
	while(isdigit(s)){x=x*10+s-'0';s=getchar();}
	x*=f;
}
int n,m,ans;
int f[108][108][108];
inline int C(int x)
{
	return ((x*(x-1))/2)%mod;
}
signed main()
{
	in(n),in(m);
	f[0][0][0]=1;
	for(R int i=1;i<=n;i++)
	{
		for(R int j=0;j<=m;j++)
		{
			for(R int k=0;k<=m-j;k++)
			{
				f[i][j][k]=f[i-1][j][k];
				if(k>=1)(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1));
				if(j>=1)(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1));
				if(k>=2)(f[i][j][k]+=f[i-1][j+2][k-2]*(((j+2)*(j+1))/2));
				if(k>=1)(f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1));
				if(j>=2)(f[i][j][k]+=f[i-1][j-2][k]*C(m-j-k+2));
				f[i][j][k]%=mod;
			}
		}
	}
	for(R int i=0;i<=m;i++)
		for(R int j=0;i+j<=m;j++)
			(ans+=f[n][i][j])%=mod;
	printf("%lld",(ans+mod)%mod);
}

「九省联考 2018」一双木棋

有一个 n×m 的棋盘，两个人轮流下棋。

一个位置可以落子当且仅当这个位置的左侧和上面都有棋子。

两个人落在对应的位置会收获各自的贡献值。

最大化自己的得分减去对方的得分。

#include<cstdio>
using namespace std;
const int P = 1e8;
long long f[14][4400];
int sta[14][4400],n,m,a[14][14];

void dfs(int u,int x,int s)\\预处理状态
{
	if (x > m)
	{
		sta[u][++sta[u][0]] = s;
		return;
	}
	dfs(u,x + 1,s);
	if (a[u][x]) dfs(u,x + 2,s | (1 << x - 1));
}
int main()
{
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d",&a[i][j]);
	for (int i = 1; i <= n; i++)
		dfs(i,1,0);
	for (int i = 1; i <= sta[1][0]; i++) f[1][i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= sta[i][0]; j++)
			for (int k = 1; k <= sta[i - 1][0]; k++)
			{
				if (sta[i][j] & sta[i - 1][k]) continue;\\排除不可能的情况
				f[i][j] = (f[i][j] + f[i - 1][k]) % P;
			}
	long long ans = 0;
	for (int i = 1; i <= sta[n][0]; i++) ans = (ans + f[n][i]) % P;
	printf("%lld\n",ans);
}

P1272 重建道路

一场可怕的地震后，人们用 $N$ 个牲口棚（编号 $1∼N$ ）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 $P$ 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

#define N 310

using namespace std;

inline int read ()
{
    int f = 1, x = 0;
    char ch;
    do {ch = getchar (); if (ch== '-') f = -1;} while (ch < '0' || ch > '9');
    do {x = x * 10 + ch - '0'; ch = getchar ();} while (ch >= '0' && ch <= '9');
    return f * x;
}

struct node
{
	int u, v, next;
} edge[N];
int n, p;
int cnt, head[N];
int f[N][N];
int a[N];
bool b[N];
int root;
int ans = 0x3f3f3f3f;

inline void add (int u, int v)
{
	edge[++cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

inline int dfs (int now)
{
	int temp; int sum = 1;
	for (int i = head[now]; i; i = edge[i].next)
	{
		int v = edge[i].v;
		temp = dfs (v); sum += temp;
		for (int j = sum; j >= 1; j --)
			for (int k = 1; k < j; k ++)
					f[now][j] = min (f[now][j], f[now][j - k] + f[v][k] - 1);
	}
	return sum;
}

int main ()
{
	n = read (); p = read ();
	int x, y;
	for (int i = 1; i <= n - 1; i ++)
	{
		x = read (); y = read ();
		a[x] ++; b[y] = 1;
		add (x, y);
	}
	memset (f, 0x3f3f3f3f, sizeof (f));
	for (int i = 1; i <= n; i ++)
	{
		if (!b[i]) root = i;
		f[i][1] = a[i];
	}
	dfs (root);
	ans = f[root][p];
	for (int i = 1; i <= n ; i ++)
	{
		if (f[i][p] < ans) ans = f[i][p] + 1;
	}
	printf ("%d", ans);
	return 0;
}

P3177 [HAOI2015] 树上染色

有一棵点数为 $n$ 的树，树边有边权。给你一个在 $0∼n$ 之内的正整数 $k$ ，你要在这棵树中选择 $k$ 个点，将其染成黑色，并将其他的 $n−k$ 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

$tot=k∗(m−k)+(sz[v]−k)∗(n−m−sz[v]+k)$

$f[u][j]=max(f[u][j],f[u][j−k]+f[v][k]+tot∗e[i].w)$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 2005
using namespace std;

inline ll read(){
	ll a=0;int f=0;char p=gc();
	while(!isdigit(p)){f|=p=='-';p=gc();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
	return f?-a:a;
}

struct ahaha{
	int w,to,next;
}e[maxn<<1];int tot,head[maxn];
inline void add(int u,int v,int w){
	e[tot].w=w,e[tot].to=v,e[tot].next=head[u];head[u]=tot++;
}

int n,m,sz[maxn];
ll f[maxn][maxn];
void dfs(int u,int fa){
	sz[u]=1;f[u][0]=f[u][1]=0;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;if(v==fa)continue;
		dfs(v,u);sz[u]+=sz[v];
		for(int j=min(m,sz[u]);j>=0;--j){   //此处倒序枚举是为了避免重复选取
			if(f[u][j]!=-1)    //在DP前应先加上当前子节点的子树纯白色的情况，这是下面也倒序枚举的前提
				f[u][j]+=f[v][0]+(ll)sz[v]*(n-m-sz[v])*e[i].w;
			for(int k=min(j,sz[v]);k;--k){
				if(f[u][j-k]==-1)continue;
				ll val=(ll)(k*(m-k)+(sz[v]-k)*(n-m-sz[v]+k))*e[i].w;   //当前情况下连接子节点的边的贡献
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+val);
			}
		}
	}
}

int main(){memset(head,-1,sizeof head);
	n=read();m=read();
	if(n-m<m)m=n-m;
	for(int i=1;i<n;++i){
		int u=read(),v=read(),w=read();
		add(u,v,w);add(v,u,w);
	}memset(f,-1,sizeof f);
	dfs(1,-1);
	printf("%lld",f[1][m]);
	return 0;
}

关于树型DP和状压DP的一些知识

1、什么是树型动态规划

2、树真的是一种特别特别优美的结构！

3、难点

选择节点类

树形背包类

树型DP求直径

P1352 没有上司的舞会

HDU 2196 Computer

POJ 1463 Strategic game

P2014 CTSC1997 选课

「SDOI2017」苹果树

[POI2008]STA-Station

POJ 3585 Accumulation Degree

[USACO10MAR]Great Cow Gathering G

「SCOI2005」互不侵犯

「NOI2001」炮兵阵地

「USACO06NOV」玉米田 Corn Fields

「九省联考 2018」一双木棋

P1272 重建道路

P3177 [HAOI2015] 树上染色

Status

Development

Support

关于树型DP和状压DP的一些知识

1、什么是树型动态规划

2、树真的是一种特别特别优美的结构！

3、难点

选择节点类

树形背包类

树型DP求直径

P1352 没有上司的舞会

HDU 2196 Computer

POJ 1463 Strategic game

P2014 CTSC1997 选课

「SDOI2017」苹果树

[POI2008]STA-Station

POJ 3585 Accumulation Degree

[USACO10MAR]Great Cow Gathering G

「SCOI2005」互不侵犯

「NOI2001」炮兵阵地

「USACO06NOV」玉米田 Corn Fields

「九省联考 2018」一双木棋

P1272 重建道路

P3177 [HAOI2015] 树上染色

Status

Development

Support

Don't have an account?

SIGN IN