企业官网建设流程全解析

背包问题

0-1背包

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+d[i]);

for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+d[i]);

n数量，m容量，w[i]代价,d[i]价值

完全背包

for(int i=1;i<=n;i++) for(int j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+d[i]);

n数量，m容量，w[i]代价,d[i]价值

多重背包问题

将每一样物品有kkk个转化成有kkk个相同的物品，每个只能选择111次即可快速转化为0−10-10−1背包类似问题快速解决题目。
普通版本

dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=0;k<=min(j,cnt[i]);k++) dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;

滚动数组优化版本

dp[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--)//一定要倒序防止污染正确数据 for(int int k=1;k<=min(j,cnt[i]);k++) dp[j]=(dp[j]+dp[j-k])%mod;

二进制拆分优化版本针对输入进行优化log级别O(nWm)−>O(nWlogm)O(nWm)->O(nW logm)O(nWm)−>O(nWlogm)
原理是基于二进制拆分可以实现所有数字的组合

for(int i=1;i<=n;i++) { cin>>v>>w>>m;//m表示个数 for(int k=1;k<=m;k*=2) { items.push_back({v*k,w*k}); m-=k; } if(m>0) items.push_back({v*m,w*m}); }

items中存储了处理完的wiw_iwi​和viv_ivi​
注意初始化和循环正负序。

基础线性DP

状压DP

状压DP基本操作

x << k将二进制下xxx每一位左移一个位置

x >> k将二进制下xxx每一位右移一个位置

s&(1<<k)判断二进制下第kkk位是不是111

s = s | (1<<k)将sss第kkk位赋值为111

s & (s<<1)判断sss相邻位置有没有111

棋盘状压DP基本套路

dp[i][j][A]表示前i行，用j个XX,当前行的状态为A时候的最佳答案

dp[i][A][B]表示前i行，当前行状态为A,前一行状态为B时候的最佳答案

转移通常为直接检查是否可以转移，然后直接进行暴力转移 dp[i][j][A]=max(dp[i][j][A],dp[i-1][j-1][B])

典型题目：P1896 P1979

TSP 状压DP基本套路

dp[S][i]表示当前去状态为S，当前位置为i时的最佳答案
枚举顺序为，当前各点状态，当前位置，下一位置。
另外应当判断所在点是否与最外重循环匹配，不匹配可直接跳过。

P1433核心代码：

for(int S=0;S<(1<<n);S++) { for(int i=0;i<n;i++)//当前所在位置 { if(!(S&(1<<i))) continue; for(int j=0;j<n;j++)//将要转移到的位置 { if(S&(1<<j)) continue; dp[S | (1<<j)][j]=min(dp[S][i]+dist(a[i],a[j]),dp[S | (1<<j)][j]); } } }

树形DP

关键区别：从线性上的递推变成了在树上进行递推，并且是从叶子节点向上向根节点进行递推。

选择节点类

dp[i][0]=dp[j][1] dp[i][1]=max(dp[j][1],dp[j][0])

树上背包

dp[v][k]=dp[u][k]+val dp[u][k]=max(dp[u][k],dp[v][k-1])

例题P2014选课

for(auto v:G[u]) { dfs(v); for(int j=m+1;j>=1;j--) for(int k=1;k<j;k++) dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]); }

换根DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响．
主要特征：会问你最佳点是哪里，状态通常定义为

dp[i]表示以i为根的答案

一般策略为：

先dfs处理一次（一般处理子树大小等不会因根不同而改变的因素）

再dfs一次进行dp求答案

P3478代码：

s[i]表示以i为节点的子树大小 void dfs(int u,int fa,int dep) { for(auto to:G[u]) { if(to==fa) continue; dfs(to,u,dep+1); s[u]+=s[to]; } s[u]+=1; dp[1]+=dep; } void dfsdp(int u,int fa) { for(auto to:G[u]) { if(to==fa) continue; dp[to]=dp[u]+(n-s[to])-(s[to]); dfsdp(to,u); } }