DP百题练（二）
目录
DP百题练（二）
相信你已经看过上一篇文章了（用于讲述简单的线性 DP 和背包）
现在我们将探讨一些高级的 DP（区间，树形，环形，状压…）
这里给出上一篇的连接：DP百题练（一）
给出下一篇的连接：DP百题练（三）
感觉难度大了很多啊，估计要咕一段时间了。。。
区间 DP
本质上来说还是线性 DP，但是具有特殊性，而且与树形 DP 有很大关联。
这类 DP 有个好处：几乎不用考虑阶段的表示，都是用两个坐标表示。（区间的左端点与右端点）
总的来说就这么多了，主要还是靠题目来理解。
设 \(f(l,r)\) 表示把最初的第 \(l\) 堆到第 \(r\) 堆合并成一堆，需要消耗的最小体力。
\(f(l,r)=min_{l\leq k<r}\{f(l,k)+f(k+1,r)\}+\sum^r_{i=l} A_i\)
初值：\(\forall l\in[1,N],f[l,l]=0\)，其余为正无穷。
目标：\(f(1,N)\)。
一定要注意 DP 的阶段、状态和决策，三者的循环一定是有外而内的。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 310
using namespace std;
int n,a[N],sum[N],f[N][N];
int main(){
scanf("%d",&n);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i]=0;
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
}
f[l][r]+=sum[r]-sum[l-1];
}
}
printf("%d\n",f[1][n]);
return 0;
}区间 DP 的好题 （但感觉也没有紫题难度啊）
在删去一条边之后，就和上一题“石子合并”十分类似，既然类似，不妨先考虑这个。
假设已经删去了一条边，题目变成了在一条链上找最大值，如果单纯只有加好，那这就和上体一模一样。
但是还有乘号，上一题的 DP 策略就没有用了。（假设两个负数的乘积 > 两个最大数的，就凉了）
所以可以记录两个值：dpmax 和 dpmin，这样就满足了 DP 的“最优子结构”。
然后再回头考虑删边的问题，其实可以破环成链并复制形成两倍长度的链。（这是 DP 遇到环形结构的常用手段）
然后上转移方程：
if(b[k+1] == 't') {
dpmax[l][r] = max(dpmax[l][r],dpmax[l][k] + dpmax[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k] + dpmin[k+1][r]);
} else {
dpmax[l][r] = max(dpmax[l][r],dpmax[l][k]*dpmax[k+1][r]);
dpmax[l][r] = max(dpmax[l][r],dpmin[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmax[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmax[k+1][r]);
}其实看到这里你就可以去打代码了。
#include <bits/stdc++.h>
using namespace std;
int a[105];
char b[105];
int dpmax[105][105];
int dpmin[105][105];
int main()
{
int n;
int ret = 0;
scanf("%d",&n);
for(int i = 1; i <= 2*n; ++i) {
if(i % 2 == 1) {
cin>>b[(i/2)+1];
b[(i/2)+1+n] = b[(i/2)+1];
}
if(i % 2 == 0) {
cin>>a[i/2];
a[i/2+n] = a[i/2];
}
}
memset(dpmax,128,sizeof(dpmax));
memset(dpmin,0x3f3f,sizeof(dpmin));
for(int i = 1; i <= 2*n; ++i) {
dpmax[i][i] = a[i];
dpmin[i][i] = a[i];
}
for(int len = 1; len <= n; ++len)
for(int l = 1; l + len <= 2*n; ++l) {
int r = l + len;
for(int k = l; k < r; ++k) {
if(b[k+1] == 't') {
dpmax[l][r] = max(dpmax[l][r],dpmax[l][k] + dpmax[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k] + dpmin[k+1][r]);
} else {
dpmax[l][r] = max(dpmax[l][r],dpmax[l][k]*dpmax[k+1][r]);
dpmax[l][r] = max(dpmax[l][r],dpmin[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmax[l][k]*dpmin[k+1][r]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmax[k+1][r]);
}
}
}
for(int i = 1; i <= n; ++i) ret = max(ret,dpmax[i][i+n-1]);
printf("%d\n",ret);
for(int i = 1; i <= n; ++i)
if(dpmax[i][i+n-1] == ret) printf("%d ",i);
return 0;
}说实话目前还没有完全理解，只能说 \(A\) 了这道题而已。
以上是思路以及算法详解。
同时注意：
对于方案技术类的动态规划问题，通常一个状态的各个决策之间满足“加法原理”， 而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。
这很重要！！！
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 310
#define MOD 1000000000
using namespace std;
int f[N][N],n;
char s[N];
int solve(int l,int r){
if(l>r) return 0;
if(l==r) return 1;
if(f[l][r]!=-1) return f[l][r];
f[l][r]=0;
if(s[l]==s[r]){
for(int k=l+2;k<=r;k++){
f[l][r]=(f[l][r]+(long long)solve(l+1,k-1)*solve(k,r)) % MOD;
}
}
return f[l][r];
}
int main(){
memset(f,-1,sizeof(f));
scanf("%s",s+1);
n=strlen(s+1);
printf("%d\n",solve(1,n));
}区间 DP入门题，感觉很简单啊
那就没啥好讲的了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 2010
using namespace std;
int n,v[N],f[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
f[i][i]=v[i]*n;
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
f[l][r]=max(f[l+1][r]+v[l]*(n-len+1),f[l][r-1]+v[r]*(n-len+1));
}
}
printf("%d\n",f[1][n]);
return 0;
}区间 DP 好题，其实没什么技术含量，主要是注意一下四点：
然后就没了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 55
using namespace std;
int n,m,sum[2*N];
int f1[2*N][2*N][15],f2[2*N][2*N][15];
int mod(int a){
return ((a%10)+10)%10;
}
int main(){
scanf("%d %d",&n,&m);
int a;
for(int i=1;i<=n;i++){
scanf("%d",&a);
sum[i]=sum[i-1]+a;
}
for(int i=n+1;i<=2*n;i++){
sum[i]=sum[i-n]+sum[n];
}
memset(f2,0x3f,sizeof(f2));
for(int i=1;i<=2*n;i++)
for(int j=i;j<=2*n;j++)
f1[i][j][1]=f2[i][j][1]=mod(sum[j]-sum[i-1]);
for(int i=2;i<=m;i++){
for(int l=1;l<=2*n;l++){
for(int r=l+i-1;r<=2*n;r++){
for(int k=l+i-2;k<r;k++){
f1[l][r][i]=max(f1[l][r][i],f1[l][k][i-1]*mod(sum[r]-sum[k]));
f2[l][r][i]=min(f2[l][r][i],f2[l][k][i-1]*mod(sum[r]-sum[k]));
}
}
}
}
int Max,Min=0x3f3f3f3f;
for(int i=1;i<=n;i++){
Max=max(Max,f1[i][i+n-1][m]);
Min=min(Min,f2[i][i+n-1][m]);
}
printf("%d\n%d\n",Min,Max);
return 0;
}思路很巧的区间 DP，好像和石子合并没什么差别。
个人认为真正的难度在于计算决策与状态的表示。
首先是决策，在手玩几组数据之后发现：
\([i,j]=[i,k]+[k+1,j]+a[i]\times a[k]\times a[j+1]\)
以上是闭区间 \([i,k]+[k+1,j]\) 的合并过程，即：
两区间合并后产生的能量=左区间第一个珠子\(\times\)右区间第一个珠子\(\times\)总区间后面的一个珠子
然后发现是不是很难看 （好像并没有），所以我们可以换一个方法。
用 \(f[l][r]\) 表示“左闭右开”区间 \([l,r)\) 的最大价值，这样我们的状态转移方程为：
\(f[l][r]=max\{f[l][k]+f[k][r]+a[l]\times a[k]\times a[r]\}\) \((l<k<r)\)
而这里就相当于合并 \(f[l][k-1]\) 与 \(f[k][r-1]\) 区间的过程。
当然，统计答案时也要更改：（与一般的 \(f[i][i+n-1]\) 不同）
\(ans=max(ans,f[i][i+n])\) \((1\leq i \leq n)\)
然后就没了：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 110
using namespace std;
int n,a[N],f[2*N][2*N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];//破环成链
}
for(int len=2;len<=n+1;len++){
for(int l=1;l<=2*n-len+1;l++){
int r=l+len-1;
for(int k=l+1;k<r;k++){
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,f[i][i+n]);
}
printf("%d\n",ans);
return 0;
}以下是我只拿 60 分的原因：（忙人请自行略过）
甲：听说这题要用高精。
乙：是吗，可是我们都不会。
甲：那怎么办，去网上找个板子吧。
乙：怎么能那么颓废，int128你会用吗。
甲：……
乙：要不我们那 60 分算了。
甲：那样不是更颓废吗。
（于是两人开始打 60 分代码，\(INF\) 年过去了）
甲：好像拿了 60 分了，接下来怎么办。
乙：看下一道题去吧。
（于是两人 颓废 离开了）
结论：
要用高精而不是取模的题目都不是好题目
——我说的
以上是一名 OIer 颓废的全过程，下面才是正题
既然只拿 60 分，我们就可以开开心心的用 long long 了。（没错，这个人已经颓废了）
这个区间 DP 唯一的独特之处就是：区间不断缩小而不是扩大。
所以阶段顺序是从大到小，而且最终答案的处理也比较特殊。
转移
当区间变为 \([i,j]\) 时，上一次取数的时候区间一定是 \([i−1,j]\) 或 \([i,j+1]\)，从这两个状态转移即可。在第 \(m−j+i−1\) 次(这个请自行模拟)取走 \(A_{i-1,j}\) 或 \(A_{i,j+1}\) 即：
\[f(i,j)=max\{f(i-1,j)+A_{i-1,j}\times 2^{m-j+i-1},f(i,j+1)+A_{i,j+1}\times 2^{m-j+i-1}\}
\]
终值（答案）
由于单个区间无法 DP ，所以答案统计时，要考虑以每个点作为最终节点的情况：
\[Ans=max_{i\leq m}\{f(i,i)+A_{i,i}\times 2^m\}
\]
至于高精…（上面已经详细讲述了我的颓废之路）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define M 100
using namespace std;
int n,m,a[M];
long long f[M][M],base[40],ans=0;
void get_base(){
base[0]=1;
for(int i=1;i<=35;i++) base[i]=base[i-1]*2;
return;
}
int main(){
scanf("%d %d",&n,&m);
get_base();
while(n--){
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
for(int j=m;j>=i;j--){
f[i][j]=max(f[i][j],f[i-1][j]+base[m-j+i-1]*a[i-1]);
f[i][j]=max(f[i][j],f[i][j+1]+base[m-j+i-1]*a[j+1]);
}
}
long long Max=0;
for(int i=1;i<=m;i++) Max=max(Max,f[i][i]+base[m]*a[i]);
ans+=Max;
}
printf("%lld\n",ans);
return 0;
}玩过 \(2048\) 就是不一样，很简单的区间 DP。
用 \(f[l][r]\) 表示 \([l,r]\) 区间内的最大值。（区间 DP 常用阶段表示）
易得状态转移方程：
\[f[l][r]=max_{l\leq k<r,f[l][k]==f[k+1][r]}\{f[l][k]+1\}
\]
然后就完事了…
哦，对了，还有就是不要忘了初始化 \(f[i][i]=a[i]\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 300
using namespace std;
int n,a[N],f[N][N],ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i]=a[i];
ans=max(ans,f[i][i]);
}
for(int len=2;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
if(f[l][k]==f[k+1][r]) f[l][r]=max(f[l][r],f[l][k]+1);
}
ans=max(ans,f[l][r]);
}
}
printf("%d\n",ans);
return 0;
}树形 DP
终于到啦树形 DP，ヾ(ﾟ∀ﾟゞ)
通过区间 DP 的学习，相信我（仅仅是相信）一定对 DP 有了初步认识。
众所周知，树形 DP 一定是在树上跑 DP ，而且一般是无根树。
在树形 DP 时：
- 一般以节点从深到浅（子树从小到大）的顺序作为 DP 的“阶段”。
- 状态表示：第一位通常是节点编号。
- 在决策时：先递归它的每个子节点，在回溯是进行状态转移。
具体还是通过习题来了解吧。
经典的树形 DP。
- \(f[x][0]\) 表示以 \(x\) 为根的子树，且 \(x\) 不参加舞会的最大快乐值。
- \(f[x][1]\) 表示以 \(x\) 为根的子树，且 \(x\) 参加了舞会的最大快乐值。
则有状态转移方程：
- \(f[x][0]=\sum_{y=son_x} max(f[y][0],f[y][1])\)。
- \(f[x][1]=\sum_{y=son_x} f[y][0]+h[x]\)。
先找到唯一的树根 \(root\)，则 \(ans=max(f[root][0],f[root][1])\)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 6060
using namespace std;
int n,h[maxn],x,y,root;
int f[maxn][5];
bool flag[maxn];
vector<int>v[maxn];
void dfs(int x){
f[x][1]=h[x];f[x][0]=0;
for(int i=0;i<v[x].size();i++){
int to=v[x][i];
dfs(to);
f[x][0]+=max(f[to][0],f[to][1]);
f[x][1]+=f[to][0];
}
return;
}
int main(){
scanf("%d",&n);
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
v[y].push_back(x);
flag[x]=true;
}
for(int i=1;i<=n;i++) if(!flag[i]){root=i;break;}//找树根
dfs(root);
printf("%d\n",max(f[root][0],f[root][1]));
return 0;
}总感觉每次做题的时候就有一大堆可说的，一道写题解时就是一两句话的事
树上背包问题典例。
用 \(f[i][j]\) 表示以 \(i\) 为根节点的子树选 \(j\) 节课的最大得分。（包括本身）
同时有一个惯用技巧：显然这是一个森林，不好处理最终答案，不妨设置一个虚节点 \(0\) 来表示根节点。
这样答案就是 \(f[0][m+1]\) 。（因为包括本身，所以是 \(m+1\)）
最后是转移方程：
\(f[i][j]=max\{f[son][k]+f[i][j-k]\}\)
特别注意：\(j=m+1\)~\(1\) ，\(k=0\)~\(j-1\)。（因为包括自己，所以最少选一个，同时最多选 \(j-1\) 个子节点）
初始化时 \(f[i][1]=score[i]\)，其余为 \(0\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,m,val[330];
int f[330][330];
vector<int>v[330];
void dfs(int now){
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
dfs(to);
for(int j=m+1;j>=1;j--){
for(int k=0;k<j;k++){
f[now][j]=max(f[now][j],f[to][k]+f[now][j-k]);
}
}
}
return;
}
int main(){
scanf("%d %d",&n,&m);
int k;
for(int i=1;i<=n;i++){
scanf("%d %d",&k,&val[i]);
f[i][1]=val[i];
v[k].push_back(i);
}
dfs(0);
printf("%d\n",f[0][m+1]);
return 0;
}树上背包问题。（分组背包）
明确 \(dp[i][j]\) 含义，表示 \(i\) 节点，选 \(j\) 个用户，能得到的钱的最大值，然后对每个节点做分组背包。
怎么看出是分组背包？首先，背包的总容量相当于该点为根节点的子树中所有的用户数量（\(dp[i][j]\) 的 \(j\) 不可能超过它连接的所有用户数）。然后，把该节点的每个儿子看成一组，每组中的元素为选一个，选两个…选n个用户。
转移方程 \(dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-\)这条边的花费) \(i,j\) 不解释了，\(v\) 表示枚举到这一组（即i的儿子），\(k\) 表示枚举到这组中的元素：选 \(k\) 个用户。
最后输出 \(dp[1][i]>=0\) 的 \(i\) 的最大值，所以反向枚举。
简单来说就是把每个节点看成一个背包啦，它的容量就是以这个节点为根的子树大小，组数就是连接的儿子个数。
每组都有很多选择，选一个，两个，三个用户，把这些选择当做组中的元素就好了。
容易看出每组中只能选一个元素，比如你选择了选一个用户，就不可能同时选择选两个用户。
然后就没有然后了啦
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 3010
using namespace std;
int n,m,head[N],cnt=0;
int f[N][N],val[N];
struct node{
int next,to,w;
}edge[N*2];
void addedge(int x,int y,int z){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
edge[cnt].w=z;
head[x]=cnt;
return;
}
int dfs(int x){
if(x>n-m){
f[x][1]=val[x];
return 1;
}
int t,sum=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
int z=edge[i].w;
t=dfs(y);sum+=t;
for(int j=sum;j>0;j--){
for(int k=1;k<=t;k++){
if(j-k>=0) f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]-z);
}
}
}
return sum;
}
int main(){
memset(f,0xcf,sizeof(f));
scanf("%d %d",&n,&m);
int k,y,z;
for(int i=1;i<=n-m;i++){
scanf("%d",&k);
for(int j=1;j<=k;j++){
scanf("%d %d",&y,&z);
addedge(i,y,z);
}
}
for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]);
for(int i=1;i<=n;i++) f[i][0]=0;
dfs(1);
for(int i=m;i>=1;i--){
if(f[1][i]>=0){
printf("%d\n",i);
return 0;
}
}
return 0;
}二次扫描与换根法详细讲解。
这道题是一个“不定根”的树形 DP 问题，此类题目是需要求出以每个节点为根的情况进行比较。
一般通过二次扫描解决一下问题：
- 第一次扫描：在“有根树”上进行一次树形 DP，也就是自底向上进行状态转移。
- 第二次扫描：从刚才选的 \(root\) 出发，对整棵树进行 \(DFS\) ，自顶向下进行推导。
首先是 \(d[]\) 数组，其实是很水的树形 DP ，自己理解吧：
\[\begin{equation}
d(x) = \sum_{y\in Son(x)}
\begin{cases}
min(d[y],c(x,y)) & y的度数 > 1\\
c(x,y) & y的度数 = 1
\end{cases}
\end{equation}\]
好了，既然你已经理解了上面的转移方程，我们就来讲讲它。（等你懂了再讲，邪恶.jpg）
其实就是说：
- 如果儿子不是叶子结点：我的最大值就 + = min（我儿子的最大值，我到儿子的边权）
- 如果儿子是叶子结点：我的最大值 + = 边权。
然后终点是二次扫描，同样先摆公式：
\[\begin{equation}
f(y) = d[y]+
\begin{cases}
min(f[x]-min(d[y],c(x,y)),c(x,y)) & x的度数>1\\
c(x,y) & x的度数 = 1
\end{cases}
\end{equation}\]
因为把 \(x\) 作为源点的总流量 \(f[x]\) ，从 \(x\) 流向 \(y\) 的流量为 \(min(d[y],c(x,y))\)。
所以 \(f[x]-min(d[y],c(x,y))\) 就是 \(x\) 流向 \(y\) 部分以外的其他部分的流量。
于是当把 \(y\) 作为源点时，\(f[y]\) 就是这个值与 \(c(x,y)\) 的最小值。（可以流向 \(x\) ，也可以流向其它地方）
当然，如果 \(x\) 是叶子结点，就直接加上 \(c(x,y)\) 的值。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 200010
using namespace std;
int T,n,cnt=0,head[N];
int d[N],f[N],ru[N];
bool vis[N];
struct node{
int next,to,val;
}edge[N*2];
void addedge(int x,int y,int z){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
edge[cnt].val=z;
head[x]=cnt;
return;
}
void dp(int x){
vis[x]=true;
d[x]=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
int z=edge[i].val;
if(vis[y]) continue;
dp(y);
if(ru[y]==1) d[x]+=z;
else d[x]+=min(z,d[y]);
}
return;
}
void dfs(int x){
vis[x]=true;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
int z=edge[i].val;
if(vis[y]) continue;
if(ru[x]==1) f[y]=d[y]+z;
else f[y]=d[y]+min(f[x]-min(d[y],z),z);
dfs(y);
}
return;
}
int main(){
scanf("%d",&T);
while(T--){
memset(vis,false,sizeof(vis));//有多组数据的题目一定要注意初始化！！！
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(ru,0,sizeof(ru));
memset(edge,0,sizeof(edge));
memset(head,0,sizeof(head));
cnt=0;
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++){
scanf("%d %d %d",&x,&y,&z);
ru[x]++;ru[y]++;
addedge(x,y,z);
addedge(y,x,z);
}
int root=1;
dp(root);
f[root]=d[root];
memset(vis,false,sizeof(vis));
dfs(root);
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
}
return 0;
}比较简单的树形 DP 吧。:happy:
就是用二次扫描与换根法来解决问题。
设：\(f[i]\) 表示以 \(i\) 为根节点的树的深度之和，\(size[i]\) 以 \(i\) 为根节点的子树大小，\(depth[i]\) 表示节点 \(i\) 的深度。
首先以 \(1\) 为根节点一遍 \(dfs\) 预处理出 \(size[i]\) 与 \(depth[i]\)。
接着二次扫描，有转台转移方程：
\[f[i]=f[fa]-2\times size[i]+n
\]
其实很好理解，当根节点由 \(fa\) 变为 \(i\) 时，那么 \(i\) 的所有结点的深度都会减 \(1\)，深度和就会减少\(size[i]\)。
同样地，所有不在 \(i\) 的子树上的结点的深度都会 \(+1\)，深度和就会加上 \(n - size[i]\)。
温馨提示：十年 OI 一场空，没开 long long 见祖宗。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1000010
using namespace std;
int n;
long long f[N],depth[N],size[N];
int head[N],cnt=0;
struct node{
int next,to;
}edge[2*N];
void addedge(int x,int y){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
return;
}
void dfs1(int x,int fa){
depth[x]=depth[fa]+1;
size[x]=1;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs1(y,x);
size[x]+=size[y];
}
return;
}
void dfs2(int x,int fa){
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
f[y]=f[x]-(size[y]<<1)+n;
dfs2(y,x);
}
}
int main(){
scanf("%d",&n);
int a,b;
for(int i=1;i<n;i++){
scanf("%d %d",&a,&b);
addedge(a,b);
addedge(b,a);
}
dfs1(1,0);
for(int i=1;i<=n;i++) f[i]=depth[i];
dfs2(1,0);
long long mx=0;
int ans;
for(int i=1;i<=n;i++){
if(f[i]>mx){
mx=f[i];ans=i;
}
}
printf("%d\n",ans);
return 0;
}感觉树形 DP 都很妙啊。
同样是采用二次扫描与换根法。
设：\(f[i][j]\) 表示距离节点 \(i\) 的距离为 \(j\) 的节点权值之和。
一次扫描：\(f[i][j]=\sum f[son_i][j-1]\)
二次扫描与换根：\(f[i][j]=f[fa_i][j-1]-f[i][j-2]\)
方程摆在这了，现在来一一解读。
首先，第一次扫描，\(f[i][j]\) 表示以 \(1\) 号节点为根时，在i这课子树中到 \(i\) 的距离为 \(j\) 的奶牛有多少只。（很简单）
第二次扫描，\(f[i][j]\) 表示以 \(i\) 节点为根时，距离它 \(j\) 个距离的节点点权之和。
那么，显然 \(f[i][j]\) 包括上一次扫描的值，但是还包括原来 \(fa_i\) 的一部分数值。
倘若：\(f[i][j]+=f[fa_i][j-1]\)，显然有重复，重复了 \(f[i][j-2]\) 的数值。（想一想为什么）
原因就是这个样子。。。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 100010
using namespace std;
int n,cnt=0,k;
int a[N],f[N][25],head[N];
struct node{
int next,to;
}edge[N*2];
void addedge(int x,int y){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
return;
}
void dfs1(int x,int fa){
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs1(y,x);
for(int j=1;j<=k;j++){
f[x][j]+=f[y][j-1];
}
}
return;
}
void dfs2(int x,int fa){
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
for(int j=k;j>=2;j--) f[y][j]-=f[y][j-2];
for(int j=1;j<=k;j++){
f[y][j]+=f[x][j-1];
}
dfs2(y,x);
}
return;
}
int main(){
scanf("%d %d",&n,&k);
int x,y;
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][0]=a[i];
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<=k;j++) ans+=f[i][j];
printf("%d\n",ans);
}
return 0;
}刚刚注册 \(BZOJ\) 账号，发现这是一个争议比较大的 \(OJ\)，但是题量和题目质量绝对是没有问题的。
简化一发题意：
给定一棵 \(n\) 个点的树，有点权，你从1号点开始一次旅行，最后回到1号点。每到达一个点，你就能获得等于该点点权的收益。但每个点都有进入该点的次数限制，且每个点的收益只能获得一次。求最大收益。\(n\leq 10^5\)
\(f(x)\) 表示从 \(x\) 出发访问 \(x\) 的子树，最后回到 \(x\)的最大收益。（树形 DP 惯用技巧）
进入该点的限制 \(k(i)\) 其实是遍历其子树的限制，最多只能遍历 \(k(i)-1\) 棵子树。
很容易想到一个贪心策略：
挑较大的 \(f[son_i]\)，当次用尽数或 \(f[son_i]<0\) 时边结束操作。（分数会减少还不如不去遍历）
如果这道题只要求求出最大值的话，已经做完了，但是好要求输出是否有多组答案，这就需要一个 \(g[]\) 记录。
用 \(g(i)\) 表示：节点 \(i\) 是否有多种方式组成最大值。
对于一个节点 \(i\)，若 \(f(i)\) 不唯一则有这三种情况：
- 其子树中我们选择的节点的答案和我们没选的答案相同。（可以替代）
- 子树中最小的答案为 \(0\)。（这就意味着我们可以不访问这颗子树）
- 已选择的子树中，有节点有多种情况。（这是必然的）
答案就是 \(f(1)\) 和 \(g(1)\)。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 100010
using namespace std;
int n,a[N],k[N],f[N],p[N];
bool g[N];
int head[N],cnt=0;
struct node{
int next,to;
}edge[N*2];
void addedge(int x,int y){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
return;
}
bool cmp(int x,int y){
return f[x]>f[y];
}
void dfs(int x,int fa){
f[x]=a[x];
int tot=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs(y,x);
}
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
p[++tot]=y;
}
sort(p+1,p+tot+1,cmp);
int q=0;
while(q<min(k[x]-1,tot) && f[p[q+1]]>=0){
f[x]+=f[p[++q]];
g[x]|=g[p[q]];
}
if(q<tot && q>0 && f[p[q]]==f[p[q+1]] || f[p[q]]==0 && q>0) g[x]=true;
return;
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&a[i]);
for(int i=2;i<=n;i++) scanf("%d",&k[i]);
k[1]=n+1;
int u,v;
for(int i=1;i<n;i++){
scanf("%d %d",&u,&v);
addedge(u,v);
addedge(v,u);
}
memset(g,false,sizeof(g));
dfs(1,0);
printf("%d\n",f[1]);
if(g[1])printf("solution is not unique\n");
else printf("solution is unique\n");
return 0;
}发现树形 DP + 贪心还蛮常见的。
设：\(f[x]\) 表示 \(x\) 子树内的最大值，\(size[x]\) 表示走完 \(x\) 的子树所花费的总时间。
那么：\(f[x]=max(f[x],f[y]+size[x]+1)\)。
其中 \(size[x]\) 存的是走完 \(y\) 之前的子树后回到 \(x\) 的时间，\(+1\) 是从 \(x\) 到 \(y\) 的花费。
（为什么不是 \(+2\) ，因为 \(c[i]\geq 1\)，所以 \(f[i]-size[i]\geq 1\)，所以 \(y\) 回到 \(x\) 的花费就被算在等待时间里了）
等待时间：根据定义 \(f[i]-size[i]\) 是用来等待的，而且等待时间总是 \(> 1\) 的。
当然，贪心策略就是，等待时间短的子树要先走。（这个很明显吧）
当然也是可以通过数学证明的：
对于两个相邻(遍历时)的子树 \(y\) 和 \(z\) ,\(y\) 前, \(z\) 后。
\(f[x]=max(f[x],size[x]+max(f[y],size[y]+2+f[z])+1)\)
对于两个相邻(遍历时)的子树 \(y\) 和 \(z\) ,\(z\) 前, \(y\) 后。
\(f[x]=max(f[x],size[x]+max(f[z],size[z]+2+f[y])+1)\)
如果交换比不交换优：
\(max(f[y],size[y]+2+f[z])<max(f[z],size[z]+2+f[y])\)
由于 \(f[y]<size[z]+2+f[y]\)，\(f[z]<size[y]+2+f[z]\)
所以上式即为：
\(size[y]+2+f[z]<size[z]+2+f[y]\)
\(f[z]-size[z]<f[y]=size[y]\)
所以，\(f[i]-size[i]\) 越小，就应越靠前。
正毕，排序即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
#include<cmath>
#define maxn 500010
using namespace std;
int n,c[maxn],u,v;
int edge[maxn],f[maxn],t[maxn];
vector<int>p[maxn];
bool cmp(int a,int b){
return edge[a]-f[a]<edge[b]-f[b];
}
void dfs(int x,int fa){
if(x!=1) f[x]=c[x];
for(int i=0;i<p[x].size();i++){
if(p[x][i]!=fa) dfs(p[x][i],x);
}
int tot=0;
for(int i=0;i<p[x].size();i++){
if(p[x][i]!=fa) t[++tot]=p[x][i];
}
sort(t+1,t+tot+1,cmp);
for(int i=1;i<=tot;i++){
f[x]=max(f[x],f[t[i]]+edge[x]+1);
edge[x]+=edge[t[i]]+2;
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<n;i++){
scanf("%d %d",&u,&v);
p[u].push_back(v);
p[v].push_back(u);
}
dfs(1,0);
printf("%d\n",max(f[1],c[1]+edge[1]));
return 0;
}树形 DP 基础啊。
为什么是蓝题，感觉好简单啊。
\(f[i][0/1]\) 表示让以 \(i\) 为根节点的子树全部合法的最少人数，其中节点 \(i\) 有/没有人。
易得状态转移方程：
\[f[i][0]+=f[son_i][1]
\]
\[f[i][1]+=min(f[i][1],f[i][0])
\]
然后就没有了。。。(´⊙ω⊙`)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define N 1510
using namespace std;
int n,head[N],f[N][2],cnt=0;
struct node{
int next,to;
}edge[N*2];
void addedge(int x,int y){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
return;
}
void dfs(int x,int fa){
f[x][0]=0;
f[x][1]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs(y,x);
f[x][0]+=f[y][1];
f[x][1]+=min(f[y][0],f[y][1]);
}
return;
}
int main(){
scanf("%d",&n);
memset(head,-1,sizeof(head));//有 0 号节点
int a,b,c;
for(int i=1;i<=n;i++){
scanf("%d %d",&a,&b);
while(b--){
scanf("%d",&c);
addedge(a,c);
addedge(c,a);//貌似也可以存单向边，无所谓了
}
}
dfs(0,-1);
printf("%d",min(f[0][0],f[0][1]));
return 0;
}简单的树形 DP。
设：\(f[i][j]\) 表示以 \(i\) 为根节点的子树去掉 \(j\) 个节点的最小删边次数。
易得转移方程：
\[f[i][j]=min_{size[i]-1\geq j>0,0\leq k\leq min(size[k],j)}\{f[son_i][k]+f[i][j-k]\}
\]
注意这里的 \(j\) 采用逆序循环，原理和背包类似，因为一种方案不可能删两次，所以采用逆序避免重复。
举个栗子：
当 \(j=10,k=5\) 时（即要删掉 \(10\) 个子节点，某棵子树可以删 \(5\) 个）
倘若正序循环，\(f[i][10]\) 将被 \(f[i][5]+f[son_i][5]\) 刷新，但是 \(f[i][5]\) 可能是被 \(f[i][0]+f[son_i][5]\) 刷新而来
那么 \(f[son_i][5]\) 将被利用两次，相当于删了两次，这显然是不可能的。
所以要用倒叙循环，避免重复。
然后再解答一个我做题时的疑惑：
Q：倒叙循环时，不是所有前面的节点都没有更新吗，那么怎么刷新数值呢？
A：第一棵子树的确没有办法刷新，但是从第二棵子树开始就不一样了。（也可以理解为一种树上背包问题）
然后注意一下答案的统计：
\[ans=min_{size[i]\geq p}\{f[i][size[i]-p]+f[i][size[i]]\}
\]
然后就快乐 \(AC\) 吧 (〃￣д￣)八(￣д￣ )
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 200
using namespace std;
int n,p,f[N][N],size[N],ans=999999999;
int head[N],cnt=0;
struct node{
int next,to;
}edge[N*2];
void addedge(int x,int y){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
return;
}
void dfs1(int x,int fa){
size[x]++;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs1(y,x);
size[x]+=size[y];
}
f[x][size[x]]=1;
f[x][0]=0;
return;
}
void dfs2(int x,int fa){
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(y==fa) continue;
dfs2(y,x);
for(int j=size[x]-1;j;j--)
for(int k=0;k<=min(j,size[y]);k++)
f[x][j]=min(f[x][j],f[y][k]+f[x][j-k]);
}
if(size[x]>=p){
ans=min(ans,f[x][size[x]-p]+f[x][size[x]]);
}
return;
}
int main(){
scanf("%d %d",&n,&p);
int a,b;
for(int i=1;i<n;i++){
scanf("%d %d",&a,&b);
addedge(a,b);
addedge(b,a);
}
memset(f,0x3f,sizeof(f));
dfs1(1,0);
f[1][size[1]]=0;
dfs2(1,0);
printf("%d\n",ans);
return 0;
}环形 DP
蛤，有环的 DP ，这…不是有后效性吗？怎么 DP？
没关系，就有这种特殊的 DP 每道题的方法都不一样但大同小异。
通过枚举把 “环形问题” 拆解成 “线性问题” 就完事了。（通常应采取适当策略，避免低效枚举）
还是通过例题来好好感受吧。ヾ(◍°∇°◍)ﾉﾞ
这就是一个有环的 DP 问题。
首先假设一天的第N小时与后一天的第一个小时不相连， 这种情况下DP转移比较好想
\(dp[i][j][0/1]\) 表示：考虑一天的前i个小时，已经休息了j小时，且第i个小时是否在休息
那么有状态转移方程：
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+a[i]);初始化为 \(dp[1][0][0]=dp[1][1][1]=0\)，其余为 \(−inf\)。
答案为 \(max(dp[n][b][0],dp[n][b][1])\)。
现在再考虑一天的第N小时与后一天的第一个小时相连。
我们发现上述转移中， 唯一没考虑到的情况只有第1个小时休息能获得体力
于是我们可以初始化 \(dp[1][1][1]=U_1\)， 转移方程与上述相同
那么答案为 \(dp[n][b][1]\)， 和前一次dp的答案比较即可得到最终结果。
到此为止在这里已经可以AC， 但是！！！
如果我们拿到POJ上提交， 你会发现自己疯狂MLE(POJ丧心病狂的 Memory limit 只有64M)
于是我们考虑用滚动数组优化空间
dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+a[i]);因为 \(dp[i][][]\) 只与 \(dp[i-1][][]\)有关， 所以只要交替使用数组第0维和第1维。
当然，如果你在洛谷上提交的话就什么问题也没有了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 4000
using namespace std;
int T,n,b,a[N],f1[N][N][2],f2[N][N][2];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&b);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(f1,0xcf,sizeof(f1));
memset(f2,0xcf,sizeof(f2));
f1[1][0][0]=f1[1][1][1]=0;
f2[1][1][1]=a[1];
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
f1[i][j][0]=max(f1[i-1][j][0],f1[i-1][j][1]);
if(j>0) f1[i][j][1]=max(f1[i-1][j-1][0],f1[i-1][j-1][1]+a[i]);
f2[i][j][0]=max(f2[i-1][j][0],f2[i-1][j][1]);
if(j>0) f2[i][j][1]=max(f2[i-1][j-1][0],f2[i-1][j-1][1]+a[i]);
}
}
printf("%d\n",max(max(f1[n][b][0],f1[n][b][1]),f2[n][b][1]));
}
return 0;
}滚动数组优化：（转载自 这篇博客）
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
typedef long long lt;
int read()
{
int x=0,f=1;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return x*f;
}
const int maxn=4010;
int t,n,m,ans;
int a[maxn];
int dp1[2][maxn][2],dp2[2][maxn][2];
int main()
{
t=read();
while(t--)
{
n=read();m=read();ans=0;
for(int i=1;i<=n;++i)a[i]=read();
memset(dp1,128,sizeof(dp1));
dp1[1][0][0]=dp1[1][1][1]=0;
memset(dp2,128,sizeof(dp2));
dp2[1][1][1]=a[1];
for(int i=2;i<=n;++i)
for(int j=0;j<=min(i,m);++j)
{
dp1[i&1][j][0]=max(dp1[(i-1)&1][j][0],dp1[(i-1)&1][j][1]);
if(j>=1)dp1[i&1][j][1]=max(dp1[(i-1)&1][j-1][0],dp1[(i-1)&1][j-1][1]+a[i]);
dp2[i&1][j][0]=max(dp2[(i-1)&1][j][0],dp2[(i-1)&1][j][1]);
if(j>=1)dp2[i&1][j][1]=max(dp2[(i-1)&1][j-1][0],dp2[(i-1)&1][j-1][1]+a[i]);
}
ans=max(dp2[n&1][m][1],max(dp1[n&1][m][1],dp1[n&1][m][0]));
printf("%d\n",ans);
}
return 0;
}其实这是一道很简单的环形 DP 问题。
根据常规操作，将环复制一遍，变成长 \(2N\) 的链。
然后发现 \(i-j>N\) 时，\(i\) 与 \(j\) 之间的配送等价于 \(i\) 与 \(j+N\) 之间的配送。（\(i>j\)）
所以问题就被简化成了：
在长为 \(2N\) 一个数列中找到 \(max\{A_i+A_j+i-j\}\)，其中 $1\leq j < i \leq N $，且 \(i-j \leq N/2\)。
因为 \(A_i+i\) 是固定的，所以再简化为：寻找 \(max\{A_j-j\}\)。（范围不变）
然后只要你懂一点单调队列的知识，这道题就没了。(๑′ᴗ‵๑)
首先介绍一个重要定理：当一个人比你小，还比你强时，你可以退役了。（很重要）
通常我把它称为OI 定理，根据定理有了以下算法：
- 开一个双端队列。（可以用 \(C++\) \(STL\) 的 \(deque\)）
- 判断队头与 \(i\) 的距离是否 \(>N/2\) ，如果是则出队。
- 此时队头就是最大的 \(A_j-j\)。
- 不断删除队尾，直到 \(A_j-j<\)队尾。（根据定理）
然后就快乐的 \(AC\) 了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<deque>
#define N 1000010
using namespace std;
int n,a[2*N];
long long ans=0;
struct node{
int t;
long long sum;
};
deque<node>q;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
q.push_front((node){1,a[1]-1});
for(int i=2;i<=2*n;i++){
while(!q.empty() && i-q.front().t>n/2) q.pop_front();
ans=max(ans,a[i]+i+q.front().sum);
while(!q.empty() && q.back().sum<=a[i]-i) q.pop_back();
q.push_back((node){i,a[i]-i});
}
printf("%lld\n",ans);
return 0;
}状压 DP
简单说就是通过一个二进制数转化成一个整数表示状态，通常这个二进制数长度 \(\leq 20\)。
这要求掌握一些位运算的技巧：
操作
技巧
取出整数 \(n\) 在二进制表示下的第 \(k\) 位
\((n>>k)\) & \(1\)
取出整数 \(n\) 在二进制表示下的第 \(0\) ~ \(k-1\) 位（后 \(k\) 位）
\(n\) & \(((1<<k)-1)\)
将整数 \(n\) 在二进制表示下的第 \(k\) 位取反
\(n\) \(xor\) \((1<<k)\)
对整数 \(n\) 在二进制表示下的第 \(k\) 位赋值为 \(1\)
$n
对整数 \(n\) 在二进制表示下的第 \(k\) 位赋值为 \(0\)
\(n\) & \((\)~\((1<<k))\)
还有一个重要的黑科技：\(lowbit\)。
\(lowbit(n)\) 表示“最低位的 \(1\) 及其后边所有的 \(0\)”。
lowbit(n)=n & (n-1)。
既然你已经会了位运算的基础技巧，就开始深入探究状压 DP 吧(～￣▽￣)～ 。
状压 DP 入门题目。
鉴于每一行的放置只和上一行有关联，更具体的说，只和上一行竖直放置的方块有关联。
我们可以考虑把行号作为 DP 的阶段，从上往下不断扩展。
设 \(f[i,j]\) 表示第 \(i\) 行的形态为 \(j\) 时，前 \(i\) 行的方案总数。（\(j\) 是十进制的 \(M\) 为二进制数）
当 \(f[i][k]==1\) 时表示：第 \(i\) 行第 \(k\) 个位置存放着竖直放置的方块的上半部分。
当 \(f[i][k]==0\) 时表示：其它情况。
那么第 \(i-1\) 行的形态 \(k\) 能转移至 \(i\) 行的形态 \(j\) 当且仅当：
- \(j\) 和 \(k\) 按位与运算结果是 \(0\)。（保证了每个竖直方块下面都可以补全）
- \(j\) 和 \(k\) 按位或运算结果是“二进制表示下有连续的偶数个 \(0\)”的整数。（保证可以用横向方块补齐整行）
只要预处理出 \([0,2^M-1]\) 中“二进制表示下有连续的偶数个 \(0\)”的整数即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 15
#define M 1<<11+10
using namespace std;
int n,m;
long long f[N][M];
bool flag[M];
int main(){
while(~scanf("%d %d",&n,&m) && n && m){
for(int i=0;i<1<<m;i++){
bool cnt=0,odd=0;
for(int j=0;j<m;j++){
if(i>>j&1) odd|=cnt,cnt=0;
else cnt^=1;
}
flag[i]=odd|cnt?false:true;
}//预处理
f[0][0]=1;//初始化
for(int i=1;i<=n;i++)
for(int j=0;j<1<<m;j++){
f[i][j]=0;//初始化
for(int k=0;k<1<<m;k++)
if((j&k)==0 && flag[j|k]) f[i][j]+=f[i-1][k];
}
printf("%lld\n",f[n][0]);//答案是 f[n][0]，想一想为什么
}
return 0;
}好强的状压 DP 啊。
首先每行只和上一行有关，所以同样是用行号作为阶段之一。
设 \(f[i,j,k]\) 表示第 \(i\) 行，状态为 \(j\) ，共用 \(k\) 个国王的方案数。
我们预先处理出每一个状态 \(sit[x]\)，以及中包含二进制下1的个数，即此状态下这一行放的国王个数 \(gs[x]\)。
于是有：
\[f[i][j][s]=\sum_{j,k合法} f[i-1][k][s-gs[i]]
\]
怎么才能算是合法呢：
- \(sit[j]\) & \(sit[k]==0\) (即上下没有重复的king)
- \(sit[j]<<1\) & \(sit[k]==0\) (即左上右下没有重复king)
- \(sit[j]\) & \(sit[k]<<1==0\) (即右上左下没有重复king)
然后就结束了。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int sit[2000],gs[2000];
int cnt=0;
int n,yong;
long long f[10][2000][100]={0};
void dfs(int he,int sum,int node)//预处理出每一个状态
{
if(node>=n)//如果已经处理完毕（注意是大于等于）
{
sit[++cnt]=he;
gs[cnt]=sum;
return;//新建一个状态
}
dfs(he,sum,node+1);//不用第node个
dfs(he+(1<<node),sum+1,node+2);//用第node个，此时node要加2，及跳过下一个格子
}
int main()
{
scanf("%d%d",&n,&yong);
dfs(0,0,0);
for(int i=1;i<=cnt;i++)f[1][i][gs[i]]=1;//第一层的所有状态均是有1种情况的
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int k=1;k<=cnt;k++)//枚举i、j、k
{
if(sit[j]&sit[k])continue;
if((sit[j]<<1)&sit[k])continue;
if(sit[j]&(sit[k]<<1))continue;//排除不合法国王情况
for(int s=yong;s>=gs[j];s--)f[i][j][s]+=f[i-1][k][s-gs[j]];//枚举s，计算f[i][j][s]
}
long long ans=0;
for(int i=1;i<=cnt;i++)ans+=f[n][i][yong];//统计最终答案，记得用long long
printf("%lld",ans);
return 0;
}好强的状压 DP 呀。
首先看数据范围，\(M\leq 10\) ，果断状压。
其实和互不侵犯那道题很类似（进阶版），但是加了个滚动数组优化。
显然 \(f[N][1<<M][1<<M]\) 会让你 \(MLE\)。
但是每行只和上两行有关，所以用滚动数组优化成 \(f[3][1<<m][1<<m]\)。
\(f[i][l][r]\) 表示第 \(i\) 行，状态压缩下的状态为 \(r\) ，上一行为 \(l\)，当二进制状态下为 \(1\) 时表示有山或有人。
有状态转移方程：
\[f[i][l][r]=max\{f[i-1][k][l]+sum[r]\}
\]
当然前提是这三个状态不会相互冲突。
首先是本序列自身不会相互冲突，以及上一列与上上列的同一列没有两个或两个以上的 \(1\)。
看不懂的话看代码吧。
当然还有一点要注意的：初始化。就是把第 \(0\) 行和第 \(1\) 行预处理出来。
for(int i=0;i<1<<m;i++)
for(int j=0;j<1<<m;j++){
if(i&j || i&(i<<1) || i&(i<<2) || j&(j<<1) || j&(j<<2) || i&a[0] || j&a[1]) continue;
f[1][i][j]=sum[i]+sum[j];
}当然 \(sum[x]\) 数组表示整数 \(x\) 在二进制状态下有几个 \(1\)，也是需要预处理的。
int get_sum(int x){
int p=0;
while(x){
if(x&1) p++;
x>>=1;
}
return p;
}代码就长这样：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int n,m,f[3][1<<10][1<<10],sum[1<<10],a[110];
int get_sum(int x){
int p=0;
while(x){
if(x&1) p++;
x>>=1;
}
return p;
}
int main(){
scanf("%d %d",&n,&m);
char c;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>c;
a[i]<<=1;
a[i]+=(c=='H'?1:0);
}
for(int i=0;i<1<<m;i++){
sum[i]=get_sum(i);
}
for(int i=0;i<1<<m;i++){
for(int j=0;j<1<<m;j++){
if(i&j || i&(i<<1) || i&(i<<2) || j&(j<<1) || j&(j<<2) || i&a[0] || j&a[1]) continue;
f[1][i][j]=sum[i]+sum[j];
}
}
for(int i=2;i<n;i++)
for(int l=0;l<(1<<m);l++){
if(l&a[i-1] || l&(l<<1) || l&(l<<2)) continue;
for(int r=0;r<(1<<m);r++){
if(l&r || r&a[i] || r&(r<<1) || r&(r<<2)) continue;
for(int fa=0;fa<(1<<m);fa++){
if(fa&l || fa&r || fa&a[i-2] || fa&(fa<<1) || fa&(fa<<2)) continue;
f[i%3][l][r]=max(f[i%3][l][r],f[(i-1)%3][fa][l]+sum[r]);
}
}
}
int ans=0;
for(int i=0;i<1<<m;i++)
for(int j=0;j<1<<m;j++)
ans=max(ans,f[(n-1)%3][i][j]);
printf("%d\n",ans);
}当然，我们发现时间和空间都很危，所以要进一步优化。
我们发现自配成功的二进制数就非常少（根据看题解高科技发现它 \(\leq 70\)），所以可以预处理出来放进一个集合。
这样讲大大减少空间与时间开销。
还有另一个黑科技：\(lowbit\)。（自行百度或者看本章开头）
在预处理时可以将 x>>=1; 换成 x-=lowbit(x) 即 x-=x & -x
#include<bits/stdc++.h>
#define N 10005
using namespace std;
const int ef[15] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192}; //调试用的2的n次方
int n, m, ans = 0, cnt = 0, a[105], s[100], num[100], dp[3][70][70];
char c[15];
inline int read() //快读
{
int red = 0, f_f = 1; char ch = getchar();
while(ch>'9'||ch<'0') {if(ch == '-') f_f = -1; ch = getchar();}
while(ch>='0'&&ch<='9') red = red * 10+ch-'0', ch = getchar();
return red * f_f;
}
int count(int x) { //求这种状态下放的士兵个数
int num = 0;
while(x) x -= x & -x, num++;
return num;
}
void pre() { //预处理函数
for(int i = 0; i < 1 << m; i++)
if(!(i & (i >> 1)) && !(i & (i << 1)) && !(i & (i << 2)) && !(i & (i >> 2))) s[++cnt] = i, num[cnt] = count(i);
}
void calc() { //dp操作区
//初始化
for(int i = 1; i <= cnt; i++) {
if((s[i] | a[1]) == a[1])
dp[1][i][0] = num[i];
}
for(int i = 1; i <= cnt; i++) { //now
for(int j = 1; j <= cnt; j++) { //lst
if((s[i] | a[2]) == a[2] && (s[j] | a[1]) == a[1] && (s[i] & s[j]) == 0)
dp[2][i][j] = num[i] + num[j];
}
}
//正式开始DP
for(int i = 3; i <= n; i++)
for(int j = 1; j <= cnt; j++) { //now
if((s[j] | a[i]) != a[i]) continue;
for(int k = 1; k <= cnt; k++) { // lst
if((s[k] | a[i-1]) != a[i-1] || (s[j] & s[k])) continue;
for(int l = 1; l <= cnt; l++) //lst`lst
if((s[l] | a[i-2]) == a[i-2] && !(s[j] & s[l]) && !(s[k] & s[l]))
dp[i%3][j][k] = max(dp[i%3][j][k], dp[(i-1)%3][k][l] + num[j]);
}
}
}
int main()
{
n = read(), m = read();
//读入处理可以放炮兵的平原
for(int i = 1; i <= n; i++) {
scanf("%s", c);
for(int j = 0; j < m; j++) {
a[i] <<= 1;
if(c[j] == 'P') a[i] += 1;
}
}
pre();
calc();
//取最大的统计答案
for(int i = 1; i <= cnt; i++) {
for(int j = 1; j <= cnt; j++) {
ans = max(ans, dp[n % 3][i][j]);
}
}
printf("%d\n", ans);
return 0;
}[USACO12MAR]Cows in a Skyscraper G
看到数据范围发现不是状压就是搜索，于是我就两个做法都用了一遍。(～￣▽￣)～
转压就用 \(f[i]\) 表示状态 \(i\) 的最小花费，\(g[i]\) 表示状态 \(i\) 下上一次还剩的体积。
状态转移方程很复杂，主要还是看代码吧。
最终答案就是 \(f[(1<<n)-1]\)。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 20
using namespace std;
int n,m,a[N],f[1<<20],g[1<<20];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(f,0x3f,sizeof(f));
memset(g,0,sizeof(g));
f[0]=1;
g[0]=m;
for(int i=0;i<(1<<n);i++){
for(int j=1;j<=n;j++){
if(i & (1<<(j-1))) continue;//如果已经包括奶牛 j 了，就不用再做一次了。
if(g[i]>=a[j] && f[i|(1<<(j-1))]>=f[i]){
f[i|(1<<(j-1))]=f[i];
if(f[i|(1<<(j-1))]==f[i]) g[i|(1<<(j-1))]=max(g[i]-a[j],g[i|(1<<(j-1))]);
else g[i|(1<<(j-1))]=g[i]-a[i];
}
else if(g[i]<a[j] && f[i|(1<<(j-1))]>=f[i]+1){
f[i|(1<<(j-1))]=f[i]+1;
if(f[i|(1<<(j-1))]==f[i]+1) g[i|(1<<(j-1))]=max(m-a[j],g[i|(1<<(j-1))]);
else g[i|(1<<j-1)]=m-a[i];
}
}
}
printf("%d\n",f[(1<<n)-1]);
return 0;
}现在来讲讲搜索，这道题我用的是迭代加深（ ID ）。
基础步骤和很简单，就是加了一个剪枝，编号为 \(i\) 的奶牛应当坐在编号 \(\leq i\) 的电梯中，
因为如果电梯总数 \(> i\)，还不如每只奶牛坐一个电梯，也只要 \(i\) 个电梯。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 20
using namespace std;
int deep=0,n,m,a[N],p[N];
bool dfs(int x){
for(int i=1;i<=deep && i<=x;i++){
if(p[i]+a[x]<=m){
p[i]+=a[x];
if(x==n) return true;
if(dfs(x+1)) return true;
p[i]-=a[x];
}
}
return false;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(1){
++deep;
memset(p,0,sizeof(p));
if(dfs(1)){
printf("%d\n",deep);
break;
}
}
return 0;
}代码短，结构清晰，而且跑得比状压快。。。（如果这不是一道 DP 题，我一定会拿搜索做的）
手机扫一扫
移动阅读更方便
你可能感兴趣的文章