「动态规划」例题之状态和转移方程的设计(2)

作者: 云中翻月 | 来源:发表于2019-02-11 12:51 被阅读20次

0x50「动态规划」例题

区间DP

线性DP从初态开始，沿着“阶段”向某个方向扩张。而区间DP是线性DP的一种，它的初态通常为长度为1的区间，每次从多个小区间向一个大区间合并，决策通常就是几个小区间的划分，它类似线段树/归并排序结构，向下划分，向上递推：先让小的区间有序，然后去让大的区间有序。（这就是DP中的最优子结构和重叠子问题）

例题

5301 石子合并
状态表示：F[i,j]表示从第i堆合并到第j堆的最小体力
转移方程：
$F[i,j]=min\left \{F[i,k]+F[k+1,j]\right \}+\sum_{p=i}^{j}A[p]，其中\; i\leq k<j$
边界： $F[i,i]=A[i]$ 其中 $\; 1\leq i\leq n$
目标： $F[1,n]$
时间复杂度： $O(n^{3})$
注意：按照从小区间往大区间递推的逻辑，区间DP时通常枚举区间长度len为阶段，枚举区间左端点i，然后根据len和i推出区间右端点j，然后len，i，j同时构成状态，最后枚举区间分割点k为决策，从小到大，从外到内依次循环。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],f[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
//  freopen("石子合并.in","r",stdin);
    cin>>n;
    memset(f,INF,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>a[i]; 
        f[i][i]=0;
        a[i]+=a[i-1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
            f[i][j]+=a[j]-a[i-1];
        }
    }
    cout<<f[1][n];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1179 Polygon
考虑两个顶点合并成一个顶点时最值的产生情况
最大值可能来源
1 两个最大值相加
2 两个最大值相乘
3 两个最小值相乘（最小值为负数）
最小值可能来源
1 两个最小值相加
2 两个最小值相乘
3 一个最大值和一个最小值相乘
4 两个最大值相乘（两个子区间的最大值和最小值都为负数的情况）
状态表示：
F[i,j,0]表示从第i个顶点合并到第j个顶点的最大值
F[i,j,1]表示从第i个顶点合并到第j个顶点的最小值
转移方程：
$F[i,j,0]=max\left\{max\left\{\begin{matrix} F[i,k,0]+F[k+1,j,0]& \\ F[i,k,0]×F[k+1,j,0] & \\ F[i,k,1]×F[k+1,j,1] & \end{matrix}\right. ，其中\; i\leq k<j \right\}$
$F[i,j,1]=min\left\{min\left\{\begin{matrix} F[i,k,1]+F[k+1,j,1]& \\ F[i,k,1]×F[k+1,j,1]& \\ F[i,k,0]×F[k+1,j,1] & \\ F[i,k,1]×F[k+1,j,0] & \\ F[i,k,0]×F[k+1,j,0] & \end{matrix}\right. ，其中\; i\leq k<j \right\}$
边界： $F[i,i,0]=F[i,i,1]=A[i]$ 其中 $\; 1\leq i\leq n$
目标： $F[1,n,0]$
时间复杂度： $O(n^{4})$ （包括枚举第一步删掉那条边）
考虑优化
破环成链，倍长数组，可以避免枚举第一步删掉那条边
时间复杂度： $O(n^{3})$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],f[maxn][maxn][2];
char op[maxn];
int main() {
    ios::sync_with_stdio(false);
//  freopen("Polygon.in","r",stdin);
    cin>>n;
    for(int i=1;i<=2*n;i++){
        if(i&1){
            cin>>op[(i+1)/2];
        }
        else{
            cin>>a[i/2];
        }
    }
    for(int i=1;i<=n;i++){
        op[i+n]=op[i];
        a[i+n]=a[i];
    }
    for(int i=1;i<=n*2;i++){
        for(int j=1;j<=2*n;j++){
            f[i][j][0]=-INF;
            f[i][j][1]=INF;
        }
    }
    for(int i=1;i<=2*n;i++) f[i][i][0]=f[i][i][1]=a[i];
//  for(int i=1;i<=2*n;i++) cout<<a[i]<<" "<<op[i]<<" ";
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n*2-len+1;i++){
            int j=i+len-1;
//          if(j-i>n) continue;
            for(int k=i;k<j;k++){
                if(op[k+1]=='x'){
                    f[i][j][0]=max(f[i][j][0],f[i][k][1]*f[k+1][j][1]);
                    f[i][j][0]=max(f[i][j][0],f[i][k][0]*f[k+1][j][0]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][1]*f[k+1][j][1]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][0]*f[k+1][j][1]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][1]*f[k+1][j][0]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][0]*f[k+1][j][0]);
                }
                else{
                    f[i][j][0]=max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
                    f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k+1][j][1]);
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,f[i][i+n-1][0]);
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        if(f[i][i+n-1][0]==ans) cout<<i<<" ";
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5302 金字塔
状态表示：F[i,j]表示S[i...j]有多少种可能的结构
转移方程：
考虑将S[i...j]分成两部分，每部分有若干棵子树，则可能产生重复计数，例如：
A|BAB|A|B|A
A|B|A|BAB|A
都会产生BAB这个子树，因此我们每次划分时，枚举S[i...j]的第一棵子树的构成，即枚举S[i...k]是第一棵子树，S[k+1...j]是其他子树
$F[i,j,0]=\left\{\begin{matrix} 0 ，S[i]\neq S[j]& \\ F[i+1,j-1]+\sum_{k=i+2}^{j-2}F[i+1,k-1]×F[k,j]，S[i]=S[j] \;且\;S[i]=S[k]\;& \end{matrix}\right.$
边界： $F[i,i]=1$ 其中 $\; 1\leq i\leq n$
目标： $F[1,n]$
时间复杂度： $O(n^{3})$
代码如下，使用的是递归计算，由于有记忆化搜索，故复杂度不会退化

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const ll mod=1e9;
const int INF=0x3f3f3f3f;
ll f[maxn][maxn];
string s;
ll dfs(ll l,ll r){
    if(l==r) return 1;
    if(l>r||s[l]!=s[r]) return 0;
    if(f[l][r]!=-1) return f[l][r];
    f[l][r]=0;
    for(int k=l+1;k<=r-1;k++){
        f[l][r]=(f[l][r]+dfs(l+1,k)*dfs(k+1,r))%mod; 
        //注意状态定义 k是该段表示的第一棵子树的切分点 所以第一棵子树的范围是[l+1,k]剩下的多个子树的范围是[k+1,r] 
    }
    return f[l][r];
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("金字塔.in","r",stdin);
    memset(f,-1,sizeof(f)); //记忆化搜索最好初始化为-1的形式 否则用f[i][j]!=0表示已访问过会超时 
    cin>>s;
    cout<<dfs(0,s.length()-1);
//  for(int i=0;i<=4;i++) for(int j=0;j<=4;j++) cout<<f[i][j]<<endl;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

树形DP

树形DP中，通常以节点从深到浅的顺序作为DP的“阶段”，状态表示中，第一维往往是节点的编号。我们常用递归的方式进行树形DP，对于节点x，首先递归其子节点，再在回溯时，从子节点向x进行状态转移。

例题

5401 没有上司的舞会
状态表示：
F[x,0]表示以x为根的子树上，x不参加的最大快乐值
F[x,1]表示以x为根的子树上，x参加的最大快乐值
转移方程：
x有两种决策
1 若x不参与，则所有子节点都可以自由选择是否参与：
$F[x,0]=\sum_{s\in Son(x)}max(F[s,0]+F[s,1])$
2 若x参与，则所有子节点都不可以参与：
$F[x,0]=H[x]+\sum_{s\in Son(x)}F[s,0]$
边界： $F[x,0]=0,F[x,1]=H[x]$
目标： $max\left\{F[root,0],F[root,1]\right\}$
时间复杂度： $O(n)$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=6000+5;
const int INF=0x3f3f3f3f;
vector<int>son[maxn];
int n,h[maxn],L,K,deg[maxn],f[maxn][2],rt;
void dfs(int x){
    f[x][0]=0,f[x][1]=h[x];
    for(int i=0;i<son[x].size();i++){
        int y=son[x][i];
        dfs(y);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("没有上司的舞会.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n-1;i++) cin>>L>>K,son[K].push_back(L),deg[L]++;
    for(int i=1;i<=n;i++) if(deg[i]==0) rt=i;
    dfs(rt);
    cout<<max(f[rt][0],f[rt][1]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5402 选课
因为每门课的先修课只有一门，所以每门课之间的依赖关系构成了一个森林。为了方便处理，新建虚拟节点0，作为森林中所有树的根节点的父节点。现在得到了一棵n+1个节点的树，其中0号节点是根节点。
仔细观察，发现这实质上是一个分组背包模型，对于每个以x为根的子树，有|Son(x)|组物品，每组物品最多可以选出一个。（每个子节点只能选择一个状态转移到x）因此进行如下的状态定义。
状态表示：
F[x,t]表示以x为根的子树上，选t门课的最优解
转移方程：
x有两种决策
1 t=0时， $F[x,t]=0$
2 t>0时，若x=0，此时因为根节点为虚拟节点，实际不需要被选修，所以背包容积为t
否则，背包容积为t-1（需要先选修x节点）
即
若x=0： $F[x,t]=\max_{\sum_{i=1}^{p}c_{i}=t}\sum_{y_{i}\in Son(x),i=1}^{p}F[y_{i},c_{i}]$
否则： $F[x,t]=\max_{\sum_{i=1}^{p}c_{i}=t-1}\sum_{y_{i}\in Son(x),i=1}^{p}F[y_{i},c_{i}]+score[x]$
边界： $F[x,0]=0$
目标： $F[0,m]$
时间复杂度： $O(m\sum_{i=1}^{n}C_{i})$
PS：本题也可以用“左子右兄”的方法建树，然后转化为二叉树DP讨论。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=300+5;
const int INF=0x3f3f3f3f;
int n,m,f[maxn][maxn],s[maxn],temp;
vector<int>son[maxn];
void dfs(int x){
    f[x][0]=0;
    for(int i=0;i<son[x].size();i++){ //循环子节点（物品） 
        int y=son[x][i];
        dfs(y);
        for(int j=m;j>=0;j--){ //倒序循环体积（保证每个物品至多选择一次） 
            for(int k=j;k>=0;k--){ //k从j开始循环（即先考虑x=0的情况） 
            //《算法竞赛进阶指南》上解释k循环倒序是为了正确处理体积为0的物品，这里暂不理解
            //从这题的数据来看，改为正序循环也能AC 
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
            }
        }
    }
    if(x!=0){ //然后再考虑x!=0的情况 
        for(int j=m;j>=1;j--) f[x][j]=f[x][j-1]+s[x];
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("选课.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>temp>>s[i];
        son[temp].push_back(i);
    }
    dfs(0);
    cout<<f[0][m];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

树形DP中还有一类问题，要求在 $O(n)$ 的时间复杂度内，求出每个节点作为根节点能够产生的最优解。解决这类问题，通常处理方法是这样：首先选择一个节点作为根节点，通过一个树上DP求出该节点的最优解，同时预处理出一个数组D[x]表示以x为根的子树的某个特征量。然后再次进行一次树上DP，对于每个节点x的子节点y，都通过D[x],D[y]等值， $O(1)$ 时间内将x的最优解转移到y，最终 $O(n)$ 扫描一次每个节点的最优解得到答案。竞赛中，这种做法称之为二次扫描和换根法。（例题：POJ 3585）

环形DP和后效性处理

因为存在重复更新，所以环上问题往往具有后效性（即难以找到一个边界/初态），因此我们需要对其做出转化。
环形问题的处理手段很直接：把环断开
朴素的做法是 $O(n)$ 枚举断开的位置
下面通过两道例题介绍两种避免枚举的方式
POJ2228 Naptime
首先假设第n个小时和第1个小时不相连，即考虑简化版的线性DP的情况
即先强制断开第n个小时和第1个小时的连接
状态表示：
F[i,j,0]表示前i个小时，睡了j个小时，第j个小时处于清醒状态的最大体力恢复值
F[i,j,1]表示前i个小时，睡了j个小时，第j个小时处于睡眠状态的最大体力恢复值
转移方程：
$F[i,j,0]=max(F[i-1,j,0],F[i-1,j,1])$
$F[i,j,1]=max(F[i-1,j-1,1]+U_{i},F[i-1,j-1,0])$
边界： $F[1,0,0]=F[1,1,1]=0$
目标： $max(F[n,B,0],F[n,B,1])$
时间复杂度： $O(nB)$
现在的状态仅仅比原先的状态少了一种情况，即第一个小时在熟睡，那么我们就强制令第n个小时和第一个小时都在睡觉再次DP（强制链接）
此时
边界： $F[1,1,1]=U_{i}$
目标： $F[n,B,1]$
则两次DP的最优值就是答案
PS：本题时限较紧，需要用滚动数组优化
代码如下，其中method_1未使用滚动数组优化，结果为TLE，method_2使用了滚动数组优化，结果为AC。

/*

*/
#define method_1
#ifdef method_1
/*
tle
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3830+5;
const int INF=0x3f3f3f3f;
int f[maxn][maxn][2],n,b,u[maxn],ans=0;
void dp(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<=b;j++){
            f[i][j][0]=max(f[i][j][0],max(f[i-1][j][0],f[i-1][j][1]));  //非滚动数组要包含f[i][j][0] 
            if(j>=1) f[i][j][1]=max(f[i][j][1],max(f[i-1][j-1][0],f[i-1][j-1][1]+u[i]));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    freopen("Naptime.in","r",stdin);
    cin>>n>>b;
    for(int i=1;i<=n;i++) cin>>u[i];
    memset(f,0xcf,sizeof(f));
    f[1][0][0]=f[1][1][1]=0;
    dp();
    ans=max(ans,max(f[n][b][0],f[n][b][1]));
    memset(f,0xcf,sizeof(f));
    f[1][1][1]=u[1];
    dp();
    ans=max(ans,f[n][b][1]);
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*
100ms ac
不知道为什么滚动数组能优化时间 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3830+5;
const int INF=0x3f3f3f3f;
int f[2][maxn][2],n,b,u[maxn],ans=0;
void dp(){
    for(int i=2;i<=n;i++){
        for(int j=0;j<=b;j++){
            f[i&1][j][0]=max(f[(i-1)&1][j][0],f[(i-1)&1][j][1]); //而滚动数组不包含f[i][j][0] 
            if(j>=1) f[i&1][j][1]=max(f[(i-1)&1][j-1][0],f[(i-1)&1][j-1][1]+u[i]);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Naptime.in","r",stdin);
    cin>>n>>b;
    for(int i=1;i<=n;i++) cin>>u[i];
    memset(f,0x80,sizeof(f));
    f[1][0][0]=f[1][1][1]=0;
    dp();
    ans=max(ans,max(f[n&1][b][0],f[n&1][b][1]));
    memset(f,0x80,sizeof(f));
    f[1][1][1]=u[1];
    dp();
    ans=max(ans,f[n&1][b][1]);
    cout<<ans;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

5501 环路运输
采用破环成链，倍长数组的方式：令 $A[i+n]=A[i]$
考虑两个仓库i，j，满足 $1\leq j < i\leq n$
1 若 $|i-j|\leq \frac{n}{2}$ ，则代价为A[i]+A[j]+|i-j|
1 若 $|i-j|> \frac{n}{2}$ ，则等价于在i和j+n之间运送，代价为A[i]+A[j+n]+|n+i-j|
因为 $n+i-j=n-(i-j)\leq \frac{n}{2}$ ，所以第二种情况可以划归到第一种情况里
即
长度为2n的道路上，要找到两个相距不超过 $\frac{n}{2}$ 的仓库，使得A[i]+A[j]+i-j最大
直接枚举i和j，时间复杂度：O( $n^{2}$ )
因此我们可以用单调递减的队列维护A[j]-j的最大值
时间复杂度： $O(n)$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e6+5;
const int INF=0x3f3f3f3f;
int n,a[maxn*2],q[maxn*2],head=0,tail=1,ans=0; 
int main() {
    ios::sync_with_stdio(false);
    //freopen("环路运输.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    q[++head]=1;
    for(int i=2;i<=2*n;i++){
        while(head<=tail&&i-q[head]>n/2) head++;
        ans=max(ans,a[i]+i+a[q[head]]-q[head]);
        while(head<=tail&&a[i]-i>a[q[tail]]-q[tail]) tail--;
        q[++tail]=i;
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

在后效性DP中还有一种情况较为复杂，往往属于期望DP，无法像上面的两种方法操作。解决这类问题的方法通常是列出转移方程后，通过高斯消元的方式求解。（例题：CodeForces24D ）

状态压缩DP

当每个状态的递推需要知道前面的所有状态时，我们往往会使用状态压缩DP。
具体地说，我们用一个n位的二进制/三进制数来表示n个物品的状态，从而通过位运算的方式高效递推。

例题

POJ2411 Mondriaan's Dream
考虑按行递推，为了表示每一行的具体状态，我们用一个m位的二进制数与行号共同构成状态。
状态表示：F[i,j]表示第i行状态为j时的方案总数。
关于状态的具体描述，若该状态第k位为1，表示第k列是竖着的1×2的长方形的上面一半，第k位为0表示其他情况。
转移方程： $F[i,j]=\sum_{j\&k=0 且 \;j|k \in S} F[i-1,k]$ ，其中S集合保存“所有二进制下每一段连续的0都有偶数个”的二进制数集合
转移方程含义：若状态k能够转移到状态j，需要满足两个条件
1 $j\&k=0$ 这保证了不会有两个上下相邻的格子都是竖着的1×2的长方形的上面一半
2 $j|k \in S$ 偶数个0表示了若干个横着的1×2的长方形，奇数个0无法分割成这样的情况
边界： $F[0,0]=1$
目标： $F[n,0]$
时间复杂度： $O(2^{m}2^{m}n)$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=11+1;
const int INF=0x3f3f3f3f;
ll n,m,f[maxn][1<<11],in_s[1<<11];
int cal(int x){ //若x的二进制中有连续奇数个0 就返回0 
//错的 因为要考虑前面有前导0  
    int cnt=0;
    while(x){
        if((x&1)==0) cnt++;
        else{
            if(cnt&1) return 0;
            cnt=0;
        }
        x>>=1;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Mondriaan's Dream.in","r",stdin);
//  D(cal(9));E; 
    while(cin>>n>>m&&n){
//      memset(s,0,sizeof(s));
        f[0][0]=1;
        for (int i = 0; i < 1 << m; i++) {
            bool cnt = 0, has_odd = 0;
            for (int j = 0; j < m; j++) //枚举每一位 考虑了前导零 
                if (i >> j & 1) has_odd |= cnt, cnt = 0;
                else cnt ^= 1;
            in_s[i] = has_odd | cnt ? 0 : 1;
        }
    //  for(int i=1;i<=16;i++){
    //      D(i);D(in_s[i]);E;
    //  }
        D(in_s[0]);E;
        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){
                        if(in_s[j|k]==1){
                            f[i][j]+=f[i-1][k];
                        }
                    }
                }
            }
        }
        cout<<f[n][0]<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1185 炮兵阵地
每一行的放置状态与前两行有关，因此做出如下状态定义
状态表示：F[i,j,k]表示第i行状态为j，第i-1行状态为k时的最大放置数。
关于状态的具体描述，若该状态第m位为1，表示第m列放置了炮兵，第m位为0表示没有放置。
转移方程：
S集合保存“所有二进制下相邻两个1的距离不小于3”的二进制数集合
cnt[x]表示x的二进制位中1的个数
valid[]保存集合S
$F[i,j,k]=\left\{\begin{matrix} \max_{a[i]\&valid[j],a[i-1]\&valid[k],valid[j]\&valid[k]=0\;并且\;valid[j]\&valid[l]=0}\left\{F[i-1,k,l] \right \}+cnt[j] & \\ -\infty \;其他情况 & \end{matrix}\right.$
边界： $F[0,0,0]=1$
目标： $\max_{a[n]\&valid[j]=0,a[n-1]\&valid[k]=0,valid[j]\&valid[k]=0}F[n,j,k]$
如果循环所有的数，时间复杂度： $O(2^{m}2^{m}2^{m}n)$
但是我们可以预处理出valid数组，即S集合，循环时只考虑集合里的数字，这样时间复杂度会变为： $O(|S|^{3}n)$
PS：本题可以进行三进制状态压缩DP，详见代码中的method_2
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=10+1;
const int INF=0x3f3f3f3f;
int n,m,f[maxn][maxn][maxn]; //本来应该是f[maxn][(1<<10)+1][(1<<10)+1] 但由于每一行的合法状态最多100个 所以可以开的很小的f数组 
int a[maxn],ans=0;
bool check(int x){
    if(x&(x<<1)) return 0;
    if(x&(x<<2)) return 0;
    return 1;
}
int popcnt[(1<<10)+1],cnt[maxn],vaild[maxn],num=0;//popcnt[i]记录i的二进制中有多少个1 
void pre(){
    for(int i=0;i<(1<<m);i++){
        popcnt[i]=popcnt[i>>1]+(i&1);
    }
    for(int i=0;i<(1<<m);i++){
        if(check(i)){
            vaild[++num]=i;
            cnt[num]=popcnt[i];
        }
    }
}
void solve(){
    /*
    for(int i=1;i<=n;i++){ //这段代码等价于下一行的一句memset 
        for(int j=1;j<=num;j++){
            for(int k=1;k<=num;k++){
                f[i][j][k]=-INF;
            }
        }
    }
    */
    memset(f,0xcf,sizeof(f));
    f[0][1][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=num;j++){
            if((a[i]&vaild[j])==0){
                for(int k=1;k<=num;k++){
                    if((a[i-1]&vaild[k])==0){
                        if((vaild[j]&vaild[k])==0){
                            for(int l=1;l<=num;l++){
                                if((vaild[j]&vaild[l])==0){
                                    f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+cnt[j]);
                                }
                            }
                            if(i==n){
                                ans=max(ans,f[n][j][k]);
                            }
                        }
                    }
                }
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("炮兵阵地.in","r",stdin);
    cin>>n>>m;
//  cout<<0xcf<<endl;
    
//  cout<<f[0][0][0];
    char ch;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch=='H'){
                a[i]|=(1<<(j-1));
            }
        }
    } 
    pre();
    solve();
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int p[11] = { 1,3,9,27,81,243,729,2187,6561,19683,59049 };
int n, m;
int f[105][59050];
char a[105][12];
int v[15];
/* 2表示放置了炮兵，2下面必须是1，1下边必须是0，同一行两个2间隔不小于3
    0
    0
0 0 2 0 0
    1
    0
*/
// 标记第row行可以填的数字的情况
// 0表示只能填0，1表示只能填1，2表示可以填2或0
void mark(int row, int last) {
    for (int i = 1; i <= m; i++, last /= 3) {
        if (last % 3 == 2) v[i] = 1; // 2的下面只能填1
        else if (last % 3 == 1) v[i] = 0; // 1的下面只能填0
        else if (a[row][i] == 'H') v[i] = 0; // 山地不能填2
        else v[i] = 2; // 既可以填2，也可以填0
    }
}

// 已知第row行的状态为last，尝试在第row+1行放炮兵
// 第row+1行搜到了第col列，状态压缩为now，放了cnt个炮兵
// 状态压缩时，第1~m列分别对应三进制数now的第0~m-1位
void dfs(int row, int col, int last, int now, int cnt) {
    if (col > m) { // 填完了当前行，DP转移
        f[row + 1][now] = max(f[row + 1][now], f[row][last] + cnt);
        return;
    }
    if (v[col] == 2) { // 填2
        int v1 = v[col + 1], v2 = v[col + 2];
        if (v[col + 1] == 2) v[col + 1] = 0; // col+1列不能填2
        if (v[col + 2] == 2) v[col + 2] = 0; // col+2列不能填2
        dfs(row, col + 1, last, now + 2 * p[col - 1], cnt + 1);
        v[col + 1] = v1, v[col + 2] = v2; // 还原现场
    }
    if (v[col] == 1)
        dfs(row, col + 1, last, now + p[col - 1], cnt); // 填1
    if (v[col] == 2 || v[col] == 0)
        dfs(row, col + 1, last, now, cnt); // 填0
}


int main() {
    //freopen("炮兵阵地.in","r",stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < p[10]; j++) {
            if (f[i][j] < 0) continue;
            mark(i + 1, j);
            dfs(i, 1, j, 0, 0);
        }
    int ans = 0;
    for (int j = 0; j < p[10]; j++) ans = max(ans, f[n][j]);
    cout << ans << endl;
}

#endif

「动态规划」例题之状态和转移方程的设计(2)

0x50「动态规划」例题

区间DP

例题

树形DP

例题

环形DP和后效性处理

状态压缩DP

例题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划