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

0x50「动态规划」例题

几点总结
1 DP三要素:状态,阶段,决策。具体地讲,若DP时是双重循环,第一重循环通常表示状态和阶段,第二重循环表示决策。若DP时是三重循环,第一重循环通常表示阶段,第二重循环和第一重循环共同组成状态,第三重循环表示决策。三者必须按照由外而内依次循环。
2 DP三条件:子问题重叠,最优子结构性质,无后效性。对于前两点,和递归的条件和性质类似,决定了DP实现的两种写法:迭代和递归。而无后效性则表示DP已经求解过的子问题不受后续影响,换言之,DP对状态空间的遍历是要求状态空间是DAG,DAG中的节点对应状态,边对应状态转移的过程,转移的选取(走哪条边)就是DP中的决策,遍历结果是DAG的一个拓扑序。(PS:若出现后效性,通常会通过一次强制链接和一次强制断开来解决,在某些环形DP/基环树问题里常见)

线性DP

线性DP指具有线性“阶段”划分的动态规划算法,若状态空间有多个维度,每个维度上都有线性变化的“阶段”,那么它就是线性DP。

经典问题

LIS

状态表示:F[i]表示以A[i]为结尾的LIS长度
转移方程:F[i]=max\left \{F[j]\right \}+1,其中 0\leq j<iA[j]<A[i]
边界:F[0]=0
目标:max\left \{F[i]\right \},其中1\leq i\leq n
时间复杂度:O(n^{2})
LIS变形问题
Q:把序列A变成单调不下降的序列,至少需要修改几个数?
A:序列A的总长度-A的最长不下降子序列长度
e.g. A={3,2,1,4,2},A的最长不下降子序列{3,4},只要把A改成{3,3,3,4,4}即可(共修改5-2=3个数)
Q:把序列A变成严格单调递增的序列,至少需要修改几个数?
A:因为保证严格单调递增,所以不能用上面的构造方法。设B[i]=A[i]-i,答案就是序列A的总长度-B的最长不下降子序列长度
e.g. A={2,2,4,3,4},则B={1,0,1,0,-1},B的最长不下降子序列{0,1},只要把B改成{-INF,0,1,INF,INF}即可,此时A={-INF+1,1,3,INF+4,INF+5}(共修改5-2=3个数)若模仿上面一题的计算方法,用A序列的总长度-A序列的LIS长度,得到答案为5-3=2错误,原因在于无法通过只改变A序列中的第三个元素4做到左右平衡。

LCS

状态表示:F[i,j]表示以A[1...i]和B[1...j]的LCS长度
转移方程:F[i,j]=max\left\{\begin{matrix} F[i-1,j] & \\ F[i,j-1] & \\ F[i-1,j-1]+1 \; \; \; if \; A[i]=B[j] & \end{matrix}\right.
边界:F[i,0]=F[0,j]=0
目标:F[n,m]
时间复杂度:O(n^{2})

数字三角形

状态表示:F[i][j]表示从左上角走到第i行第j列的最大和
转移方程:F[i,j]=A[i,j]+max\left\{\begin{matrix} F[i-1,j] & \\ F[i-1,j-1] \; \; \; if \; j>1& \end{matrix}\right.
边界:F[1,1]=A[1,1]
目标:max\left \{F[n,j]\right \},其中1\leq j \leq n
时间复杂度:O(n^{2})

例题

POJ2279 Mr Young's Picture Permutations

我们将所有人按照从高到低的顺序放入整个序列中,这样就有了DP的顺序。
状态表示:F[a1,a2,a3,a4,a5]表示各排从左端起分别站了a1,a2,a3,a4,a5人的方案数量
转移方程:
若\;a1<n1,F[a1+1,a2,a3,a4,a5]+=F[a1,a2,a3,a4,a5]
若\;a2<a1\;且\;a2<n2,F[a1,a2+1,a3,a4,a5]+=F[a1,a2,a3,a4,a5]
3~5排同理
边界:F[0,0,0,0,0]=1
目标:F[n1,n2,n3,n4,n5]
时间复杂度:O(n^{5})

/*

*/
#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=30+1;
const int maxk=5+5;
const int INF=0x3f3f3f3f;
ll f[maxn][maxn][maxn][maxn][maxn],k,num[maxk];
int main() {
    ios::sync_with_stdio(false);
//  freopen("Mr Young's Picture Permutations.in","r",stdin);
    while(cin>>k&&k) {
        memset(num,0,sizeof(num));
        //memset(f,0,sizeof(f));
        f[0][0][0][0][0]=1;
        for(int i=1; i<=k; i++) {
            cin>>num[i];
        }
        for(ll a1=1; a1<=num[1]; a1++) {
            for(ll a2=0; a2<=min(num[2],a1); a2++) {
                for(ll a3=0; a3<=min(num[3],a2); a3++) {
                    for(ll a4=0; a4<=min(num[4],a3); a4++) {
                        for(ll a5=0; a5<=min(num[5],a4); a5++) {
                            ll &p=f[a1][a2][a3][a4][a5];
                            p=0;
                            if(a1-1>=a2) p+=f[a1-1][a2][a3][a4][a5];
                            if(a2-1>=a3) p+=f[a1][a2-1][a3][a4][a5];
                            if(a3-1>=a4) p+=f[a1][a2][a3-1][a4][a5];
                            if(a4-1>=a5) p+=f[a1][a2][a3][a4-1][a5];
                            if(a5-1>=0) p+=f[a1][a2][a3][a4][a5-1];
                        }
                    }
                }
            }
        }
        cout<<f[num[1]][num[2]][num[3]][num[4]][num[5]]<<endl;
    }

    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5101 LCIS
状态表示:F[i,j]表示以A[1...i]和B[1...j]构成的以B[j]结尾的LCIS长度
转移方程:
F[i,j]=max\left\{\begin{matrix} F[i-1,j] \;if \; A[i] \neq B[j]& \\ F[i,k] \; if \; A[i]=B[j] ,0\leq k < j ,B[k]<B[j]& \end{matrix}\right.

F[i,j]=max\left\{\begin{matrix} F[i-1,j] \;if \; A[i] \neq B[j]& \\ F[i,k] \; if \; A[i]=B[j] ,0\leq k < j ,B[k]<A[i]& \end{matrix}\right.
边界:F[i,0]=F[0,j]=0
目标:max\left\{F[n,j]\right\}
朴素实现这个转移方程,复杂度为O(n^{3})
但是我们自己观察这个方程,会发现当第二层循环变量j时,我们可以将第一层循环变量i视为定值,这让B[k]<A[i]这个条件是固定的。这意味着当j+1时,k的取值范围从[0,j)变成了[0,j+1),也就是说,这时决策集合的下界不变,上界最多增加一个可能的最优决策,那么我们只要O(1)判断这个B[j]<A[i]是否满足即可确定新的j能否有可能产生最优决策。
具体实现上,我们在每次进入第一层循环时,维护一个变量val表示决策集合中F[i-1,k]的最大值,在每次j的范围增大时,判断j能否进入决策集合即可。这样的操作避免了重复扫描,时间复杂度O(n^{2}),代码如下,其中method_1为朴素算法,method_2为优化算法。

/*

*/
#define method_2
#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=3000+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][maxn],a[maxn],b[maxn],ans=0;
int main() {
    ios::sync_with_stdio(false);
    //freopen("LCIS.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i]==b[j]){
                for(int k=0;k<j;k++){
                    if(b[k]<a[i]){
                        f[i][j]=max(f[i-1][k]+1,f[i][j]);
                    }
                }
            }
            else f[i][j]=f[i-1][j];
            if(i==n) ans=max(ans,f[n][j]);
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/
#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=3000+5;
const int INF=0x3f3f3f3f;
int n,f[maxn][maxn],a[maxn],b[maxn],ans=0;
int main() {
    ios::sync_with_stdio(false);
//  freopen("LCIS.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        int val=0;
        if(b[0]<a[i]) val=max(val,f[i-1][0]);
        for(int j=1;j<=n;j++){
            if(a[i]==b[j]){
                f[i][j]=val+1;
            }
            else f[i][j]=f[i-1][j];
            if(b[j]<a[i]) val=max(val,f[i-1][j]);
            if(i==n) ans=max(ans,f[n][j]);
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

5102 Mobile Service
状态表示:F[i,x,y,z]表示完成了前i个请求,三个服务员分别在x,y,z位置的最小花费
转移方程:
F[i+1,p_{i+1},y,z]=min(F[i+1,p_{i+1},y,z],F[i,x,y,z]+c(x,p_{i+1}))
F[i+1,x,p_{i+1},z]=min(F[i+1,x,p_{i+1},z],F[i,x,y,z]+c(y,p_{i+1}))
F[i+1,x,y,p_{i+1}]=min(F[i+1,x,y,p_{i+1}],F[i,x,y,z]+c(z,p_{i+1}))
题目要求同一位置不能有多个员工,所以要用if语句判断转移合法性
边界:F[0,1,2,3]=0
目标:max\left\{F[n,x,y,z]\right\}
按照这个方程,时间复杂度O(nL^{3})
但是仔细观察会发现,当完成前i个请求时,必然有一个员工位于p_{i}位置,因此只需要知道i和两名员工的位置,就可以推出第三个员工的位置,即消去了冗余状态
故更改定义如下
状态表示:F[i,x,y]表示完成了前i个请求,两个服务员分别在x,y位置的最小花费(第三个员工在p_{i}位置)
转移方程:
F[i+1,p_{i},y]=min(F[i+1,p_{i},y],F[i,x,y]+c(x,p_{i+1})) //x去处理请求
F[i+1,x,p_{i}]=min(F[i+1,x,p_{i}],F[i,x,y]+c(y,p_{i+1})) //y去处理请求
F[i+1,x,y]=min(F[i+1,x,y],F[i,x,y]+c(p_{i},p_{i+1})) //p_{i}去处理请求
题目要求同一位置不能有多个员工,所以要用if语句判断转移合法性
边界:F[0,1,2]=0
目标:max\left\{F[n,x,y]\right\}
按照这个方程,时间复杂度:O(nL^{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=1000+5;
const int maxl=200+5;
const int INF=0x3f3f3f3f;
int l,n,f[maxn][maxl][maxl],c[maxl][maxn],p[maxn];
int main() {
    ios::sync_with_stdio(false);
//  freopen("Mobile Service.in","r",stdin);
    cin>>l>>n;
    for(int i=1; i<=l; i++) {
        for(int j=1; j<=l; j++) {
            cin>>c[i][j];
        }
    }
    for(int i=1; i<=n; i++) cin>>p[i];
    memset(f,INF,sizeof(f));
    f[0][1][2]=0;
    p[0]=3;
    int ans=INF;
    for(int i=1; i<=n; i++) {
        for(int x=1; x<=l; x++) {
            for(int y=1; y<=l; y++) {
                if(x==y) continue;
                if(f[i-1][x][y]==INF) continue;
                int z=p[i-1];
                if(x!=p[i]&&y!=p[i])f[i][x][y]=min(f[i-1][x][y]+c[z][p[i]],f[i][x][y]);
                if(z!=p[i]&&y!=p[i])f[i][z][y]=min(f[i-1][x][y]+c[x][p[i]],f[i][z][y]);
                if(x!=p[i]&&z!=p[i])f[i][x][z]=min(f[i-1][x][y]+c[y][p[i]],f[i][x][z]);
                //  if(i==n) ans=min(ans,f[n][x][y]); 
                //不能在这里更新 因为f[n][x][y]可能尚未达到最优解,因为后面两个维度不一定保证递增
            }
        }
    }
    for(int x=1; x<=l; x++)
        for(int y=1; y<=l; y++)
            ans=min(ans,f[n][x][y]);
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ3666 Making the Grade
引理:记答案为S,则在满足S最小的前提下,一定存在一种构造B序列的方案,使得B中的数值都在A中出现过。
状态表示:F[i]表示已经构造好前i个数,以B[i]为结尾的序列的最小S值,即此时B[i]=A[i]
转移方程:F[i]=min\left \{F[j]+cost(j+1,i-1)\right \},其中 0\leq j < iA[j] \leq A[i]
cost(j+1,i-1)表示构造B[j+1]...B[i-1]满足A[j]\leqB[j+1]\leq...\leqB[i-1]\leqA[i]时,\sum_{k=j+1}^{i-1}|A[k]-B[k]|的最小值
方程解释:DP方程中的i就是最新的一段数中与A相同的位置,j是上一段数中这样的位置,因此cost(j+1,i-1)就是把区间中前一部分变成A[j]后一部分变成A[i]的最小代价。
边界:F[0]=0
目标:F[n]
时间复杂度:O(n^{3}),其中计算cost的时间复杂度:O(n)
考虑优化cost的计算过程,我们做如下的状态定义
状态表示:F[i,j]表示已经构造好前i个数,以B[i]=j为结尾的序列的最小S值,即此时B[i]=A[i]=j
转移方程:F[i,j]=min\left \{F[i-1,k]\right \}+|A[i]-j|,其中 0\leq k \leq j
边界:F[0,i]=0,其中 0\leq i \leq 2^{31}
目标:min\left\{F[n,i]\right\},其中 0\leq i \leq 2^{31}
时间复杂度:O(n^{2}×2^{31})
空间复杂度:O(n×2^{31})
考虑优化时间和空间复杂度
1 离散化A序列
时间复杂度:O(n^{3})
空间复杂度:O(n^{2})
2 类比之前LCIS的转移方程,这里变量k的变化,即决策集合的变化仍满足随着j的增大只增不减的性质,所以做出同样的优化。
时间复杂度:O(n^{2})
空间复杂度:O(n^{2})
代码如下,其中method_1仅仅进行了离散化,结果为TLE。method_2进行了上述两种优化,结果为AC。

/*

*/
#define method_2
#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=2000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],b[maxn],f[maxn][maxn],cnt;
int main() {
    ios::sync_with_stdio(false);
    freopen("Making the Grade.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    /*
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    }
    */
    int ans=INF;
    memset(f,INF,sizeof(f));
    for(int i=1;i<=cnt;i++) f[0][i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            for(int k=1;k<=j;k++){
                f[i][j]=min(f[i-1][k]+abs(a[i]-b[j]),f[i][j]);
            }
            if(i==n) ans=min(ans,f[n][j]);
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/
#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=2000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],b[maxn],f[maxn][maxn],cnt;
int main() {
    ios::sync_with_stdio(false);
//  freopen("Making the Grade.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;
    /*
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    }
    */
    int ans=INF;
    memset(f,INF,sizeof(f));
    for(int i=0;i<=cnt;i++) f[0][i]=0;
    for(int i=1;i<=n;i++){
        int val=f[i-1][0];
        for(int j=1;j<=cnt;j++){
            val=min(val,f[i-1][j]);
            f[i][j]=val+abs(a[i]-b[j]);
            if(i==n) ans=min(ans,f[n][j]);
        }
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

5103 传纸条
从左上角走到右下角一个来回 等价于 两个人同时从左上角出发走到右下角
状态表示:F[x1,y1,x2,y2]表示第一个人在(x1,y1)第二个人在(x2,y2)的最大收益
此时时间复杂度:O(n^{4})
考虑优化
观察后发现,设目前路径长度为i,则x1+y1=x2+y2=i+2(因为两人同时行走)
所以通过i,x1,x2就可以确定y1,y2
修改状态表示如下
状态表示:F[i,x1,x2]表示第一个人在x1行,第二个人在x2行,目前路径长度为i的最大收益(此时y1=i+2-x1,y2=i+2-x2)
转移方程:每个人有两种移动方式,两个人移动状态共有四种,这里以两人均向右为例:
即两人从(x1,y1)(x2,y2)走向(x1,y1+1)(x2,y2+1)
若x1=x2且y1+1=y2+1,说明两人路径在此处相交,答案累加一次:
F[i+1,x1,x2]=max\left \{F[i+1,x1,x2],F[i,x1,x2]+A[x1,y1+1]\right \}
否则分别累加答案:
F[i+1,x1,x2]=max\left \{F[i+1,x1,x2],F[i,x1,x2]+A[x1,y1+1]+A[x2,y2+1]\right \}
边界:F[0,1,1]=A[1,1]
目标:F[n+m-2,n,n]
时间复杂度:O((n+m)n^{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=50+5;
const int INF=0x3f3f3f3f;
int a[maxn][maxn],f[maxn*2][maxn][maxn],n,m;
int main() {
    ios::sync_with_stdio(false);
//  freopen("传纸条.in","r",stdin);
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    f[0][1][1]=a[1][1];
    for(int i=1; i<=n+m-2; i++) {
        for(int j=1; j<=min(n,i+1); j++) {
            for(int k=1; k<=min(n,i+1); k++) {
                int Y1=i+2-j;
                int Y2=i+2-k;
                if((Y1>=1&&Y1<=m)&&(Y2>=1&&Y2<=m)) {
                    if(j==k&&Y1==Y2) {
                        f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a[j][Y1]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+a[j][Y1]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+a[j][Y1]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+a[j][Y1]);
                    } else {
                        f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a[j][Y1]+a[k][Y2]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+a[j][Y1]+a[k][Y2]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]+a[j][Y1]+a[k][Y2]);
                        f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+a[j][Y1]+a[k][Y2]);
                    }
                }
            }
        }
    }
    cout<<f[n+m-2][n][n];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5104 I-country
考虑凸连通块性质:任何一个凸连通块可以划分成若干行,每行的左端点列号先减小后增大,右端点列号先增大后减小。
状态表示:F[i,j,l,r,x,y]表示前i行,选了j个格子,其中第i行选了第l到r的格子,左轮廓的单调性是x,右轮廓的单调性是y(0表示递增,1表示递减)时,能构成的凸连通块的最大权值和
转移方程:其中A为每行的前缀和数组,即\sum_{p=l}^{r}A[i,p]=A[i][r]-A[i][l-1]
1.左边界列号递减,右边界列号递增(两边界都处于扩张状态)
F[i,j,l,r,1,0] =A[i][r]-A[i][l-1]+\left\{\begin{matrix} max\left \{F[i-1,j-(r-l+1),p,q,1,0]\right \}\;\;if\;j>r-l+1>0 \;\;其中\; l\leq p\leq q\leq r& \\ F[i-1,0,0,0,1,0]\;\;if\;j=r-l+1>0& \end{matrix}\right.
2.左右边界列号都递减(左边界扩张,右边界收缩)
F[i,j,l,r,1,1] = A[i][r]-A[i][l-1] + max\left\{max\left\{F[i-1,j-(r-l+1),p,q,1,y]\right \}(0\leq y\leq 1)\right \}
3.左右边界列号都递减(左边界收缩,右边界扩张)
F[i,j,l,r,0,0] = A[i][r]-A[i][l-1] + max\left\{max\left\{F[i-1,j-(r-l+1),p,q,x,0](0\leq x\leq 1)\right \}\right \}
4.左边界列号递增,右边界列号递减(两边界都处于收缩状态)
F[i,j,l,r,0,1] = A[i][r]-A[i][l-1] + max\left\{max\left\{max\left\{F[i-1,j-(r-l+1),p,q,x,y]\right \}(0\leq y\leq 1)\right \}(0\leq x\leq 1)\right \}(p\leq l\leq r\leq q)
边界:F[i,0,0,0,1,0]=0
目标:max\left \{F[i,K,l,r,x,y]\right \}
时间复杂度:O(n^{2}×m^{5})
本题还需要输出方案,对于DP问题输出方案,通常是使用一个/多个与F数组同样大小的数组来记录每一次转移的最优解的取值,然后在DP结束后,从终态向初态递归,依次在回溯时输出答案。
代码如下,其中method_1没有输出方案,method_2输出方案

/*

*/
#define method_2
#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=15+2;
const int maxk=225+5;
const int INF=0x3f3f3f3f;
int n,m,k,a[maxn][maxn],s[maxn][maxn],f[maxn][maxk][maxn][maxn][2][2];
/*
f[i][j][l][r][x][y] 表示前i行 占据了j个格子 第i行从l列到r列 左端点状态为x 右端点状态为y 的最大权值
x=0 表示列号递增 x=1 表示列号递减
*/
int main() {
    ios::sync_with_stdio(false);
    freopen("I-country.in","r",stdin);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
            s[i][j]=s[i][j-1]+a[i][j];
        }
    }
//  cout<<s[2][3]<<endl;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=k; j++) {
            for(int l=1; l<=m; l++) {
                for(int r=l; r<=m; r++) {
                    if(j-(r-l+1)<0) break;
                    for(int p=l; p<=r; p++) {
                        for(int q=p; q<=r; q++) {
                            f[i][j][l][r][1][0]=max(f[i][j][l][r][1][0],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
                        }
                    }
                    for(int p=l; p<=r; p++) {
                        for(int q=r; q<=m; q++) {
                            f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
                            f[i][j][l][r][1][1]=max(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1]);
                        }
                    }
                    for(int p=1; p<=l; p++) {
                        for(int q=l; q<=r; q++) {
                            f[i][j][l][r][0][0]=max(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
                            f[i][j][l][r][0][0]=max(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1]);
                        }
                    }
                    for(int p=1; p<=l; p++) {
                        for(int q=r; q<=m; q++) {
                            f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][0][1]+s[i][r]-s[i][l-1]);
                            f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1]);
                            f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1]);
                            f[i][j][l][r][0][1]=max(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1]);
                        }
                    }
                }
            }
        }
    }
    int ans=-INF;
    for(int i=1; i<=n; i++) {
        for(int l=1; l<=m; l++) {
            for(int r=l; r<=m; r++) {
                for(int x=0; x<=1; x++) {
                    for(int y=0; y<=1; y++) {
                        ans=max(ans,f[i][k][l][r][x][y]);
                    }
                }
            }
        }
    }
    cout<<"Oil : "<<ans<<endl;
    return 0;
}
#endif
#ifdef method_2
/*

*/
#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=15+2;
const int maxk=225+5;
const int INF=0x3f3f3f3f;
int n,m,k,a[maxn][maxn],s[maxn][maxn],f[maxn][maxk][maxn][maxn][2][2];
/*
f[i][j][l][r][x][y] 表示前i行 占据了j个格子 第i行从l列到r列 左端点状态为x 右端点状态为y 的最大权值
x=0 表示列号递增 x=1 表示列号递减
*/
struct method{
    int l,r,x,y;
}met[maxn][maxk][maxn][maxn][2][2];
int ai,aj,al,ar,ax,ay;
void update(int now,int l,int r,int x,int y){
    int &ans=f[ai][aj][al][ar][ax][ay];
    method &p=met[ai][aj][al][ar][ax][ay];
    if(ans>=now) return;
    ans=now;
    p.l=l;
    p.r=r;
    p.x=x;
    p.y=y;
}
void print(int i,int j,int l,int r,int x,int y){
    if(j==0) return;
    method &p=met[i][j][l][r][x][y];
    print(i-1,j-(r-l+1),p.l,p.r,p.x,p.y);
    for(int ii=l;ii<=r;ii++){
        cout<<i<<" "<<ii<<endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("I-country.in","r",stdin);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
            s[i][j]=s[i][j-1]+a[i][j];
        }
    }
//  cout<<s[2][3]<<endl;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=k; j++) {
            for(int l=1; l<=m; l++) {
                for(int r=l; r<=m; r++) {
                    if(j-(r-l+1)<0) break;
                    ai=i;
                    aj=j;
                    al=l;
                    ar=r;
                    ax=1;
                    ay=0;
                    for(int p=l; p<=r; p++) {
                        for(int q=p; q<=r; q++) {
                            update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
                        }
                    }
                    ax=1;
                    ay=1;
                    for(int p=l; p<=r; p++) {
                        for(int q=r; q<=m; q++) {
                            update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
                            update(f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1],p,q,1,1);
                        }
                    }
                    ax=0;
                    ay=0;
                    for(int p=1; p<=l; p++) {
                        for(int q=l; q<=r; q++) {
                            update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
                            update(f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1],p,q,0,0);
                        }
                    }
                    ax=0;
                    ay=1;
                    for(int p=1; p<=l; p++) {
                        for(int q=r; q<=m; q++) {
                            update(f[i-1][j-(r-l+1)][p][q][1][0]+s[i][r]-s[i][l-1],p,q,1,0);
                            update(f[i-1][j-(r-l+1)][p][q][1][1]+s[i][r]-s[i][l-1],p,q,1,1);
                            update(f[i-1][j-(r-l+1)][p][q][0][0]+s[i][r]-s[i][l-1],p,q,0,0);
                            update(f[i-1][j-(r-l+1)][p][q][0][1]+s[i][r]-s[i][l-1],p,q,0,1);
                        }
                    }
                }
            }
        }
    }
    int ans=-INF;
    for(int i=1; i<=n; i++) {
        for(int l=1; l<=m; l++) {
            for(int r=l; r<=m; r++) {
                for(int x=0; x<=1; x++) {
                    for(int y=0; y<=1; y++) {
                        if(f[i][k][l][r][x][y]>ans){
                            ans=f[i][k][l][r][x][y];
                            ai=i;
                            al=l;
                            ar=r;
                            ax=x;
                            ay=y;
                        }
                    }
                }
            }
        }
    }
    cout<<"Oil : "<<ans<<endl;
    print(ai,k,al,ar,ax,ay);
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

5105 Cookies
引理:贪婪度大的孩子饼干多。
证明:将所有孩子按照贪婪度降序排序,获得的饼干数单调递减。若交换两个相邻的孩子g[i]和g[i+1](邻项交换,满足g[i]>g[i+1]),则原来两个孩子产生的怨气是g[i]×(i-1)+g[i+1]×i,交换后产生的怨气是g[i+1]×(i-1)+g[i]×i,即会对答案产生g[i]-g[i+1]的贡献,而其他孩子的怨气不变,所以经过反证法,交换后的结果显然不优于原单调序列。
根据引理,我们将所有孩子的贪婪度递减排序,从左向右DP。
至此,我们已经通过额外的算法确定了DP顺序,现在考虑如何表示状态。
状态表示:F[i,j]表示给前i个孩子分配j块饼干的最小怨气和
我们做出如下转化
1 若第i个孩子饼干数为1,则枚举i前面有多少孩子的饼干数也为1(这些孩子不会对第i个孩子产生贡献)
2 若第i个孩子的饼干数大于1,则等价于分配j-i块饼干给前i个孩子,每人少拿一块饼干,饼干相对数量不变,故答案不变。
状态表示:F[i]表示以A[i]为结尾的LIS长度
转移方程:
F[i,j] =min\left\{\begin{matrix} min\left\{F[k,j-(i-k)]+k*\sum_{p=k+1}^{i}g[p]\right \} \;其中\;0\leq k <i\;\;(转化\;1)& \\ F[i,j-i] (转化\;2)& \end{matrix}\right.
PS:解释下转化1的转移方程,枚举k表示[k+1,i]的孩子也是一块饼干,那么[k+1,i]的孩子总共获得了i-k块饼干,剩余饼干数就是j-(i-k)。与此同时,前k个孩子获得的饼干数大于一块,所以后面的[k+1,i]个孩子会因此产生怨气,怨气值为k×g[k+1]+k×g[k+2]+...+k×g[i]=k×\sum_{p=k+1}^{i}g[p]
边界:F[0,0]=0
目标:F[n,m]
时间复杂度:O(n^{2}*m)
这题输出方案的方式和上一题类似,故不再赘述
代码如下 ,其中method_1没有输出方案,method_2输出方案

/*

*/
#define method_2
#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=30+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,g[maxn],f[maxn][maxm],s[maxn];
bool cmp(int x,int y){
    return x>y;
}
int main() {
    ios::sync_with_stdio(false);
    freopen("Cookies.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>g[i];
    sort(g+1,g+n+1,cmp);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+g[i];
    memset(f,INF,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=m;j++){
            f[i][j]=min(f[i][j],f[i][j-i]);
            for(int k=0;k<i;k++){
                f[i][j]=min(f[i][j],f[k][j-(i-k)]+k*(s[i]-s[k]));
            }
        }
    }
    cout<<f[n][m];
    return 0;
}
#endif
#ifdef method_2
/*

*/
#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=30+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,g[maxn],f[maxn][maxm],s[maxn],c[maxn],a[maxn][maxm],b[maxn][maxm],ans[maxn];
bool cmp(int x,int y){
    return g[x]>g[y];
}
void print(int n,int m){
    if(n==0) return;
    print(a[n][m],b[n][m]);
    if(a[n][m]==n){
        for(int i=1;i<=n;i++) ans[c[i]]++;
    } 
    else{
        for(int i=a[n][m]+1;i<=n;i++) ans[c[i]]=1;
    }
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("Cookies.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>g[i],c[i]=i;
    sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+g[c[i]];
    memset(f,INF,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=m;j++){
            f[i][j]=f[i][j-i];
            a[i][j]=i;
            b[i][j]=j-i;
            for(int k=0;k<i;k++){
                if(f[i][j]>f[k][j-(i-k)]+k*(s[i]-s[k])){
                    f[i][j]=f[k][j-(i-k)]+k*(s[i]-s[k]);
                    a[i][j]=k;
                    b[i][j]=j-(i-k);
                }
            }
        }
    }
    cout<<f[n][m]<<endl;
    print(n,m);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

背包DP

背包问题是线性DP中的一类特殊模型。

经典问题

01背包

状态表示:F[i,j]表示从前i个物品中选出总体积为j的物品放入背包
转移方程:
F[i,j]=max\left\{\begin{matrix} F[i-1,j] \;\; 不选择第\;i\;个物品 & \\ F[i-1,j-V_{i}]+W_{i} \;\; 选择第\;i\;个物品& \end{matrix}\right.
边界:F[0,0]=0
目标:max\left \{F[n,j]\right \},其中0\leq j \leq m
时间复杂度:O(nm)
空间复杂度:O(nm)
代码如下

memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++)
        f[i][j] = f[i - 1][j];
    for (int j = v[i]; j <= m; j++)
        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}

考虑优化空间复杂度
因为每一阶段的i的状态之和i-1的状态有关,所以可以用滚动数组优化
时间复杂度:O(nm)
空间复杂度:O(2m)
代码如下

int f[2][MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++)
        f[i & 1][j] = f[(i - 1) & 1][j];
    for (int j = v[i]; j <= m; j++)
        f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; j++)
    ans = max(ans, f[n & 1][j]);

考虑继续优化
实现转移方程时,每次都会进行一次从F[i-1][]到F[i][]的拷贝,这提示我们直接省略F数组的第一维
时间复杂度:O(nm)
空间复杂度:O(m)
代码如下

int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++)
    ans = max(ans, f[j]);

对于为什么j为倒序循环的解释:
F数组的后半部分F[j...m]处于第i个阶段,也就是已经考虑过放入第i个物品的情况。
F数组的前半部分F[0...j-1]处于第i-1个阶段,也就是尚未考虑过放入第i个物品的情况。
随着j的不断减小,我们不断用第i-1个阶段的状态F[j - v[i]]来更新F[j],就保证了第i个物品最多可能被放入背包一次。
如果j正序循环,可能导致如下情况,F[j]被F[j-v[i]]+w[i]更新,接下来j增大到j+v[i]时,F[j+v[i]]又被F[j]+w[i]更新,即两个同时处于第i个阶段的状态产生了转移,相当于第i个物品被使用了两次。

完全背包

状态表示:F[i,j]表示从前i个物品中选出总体积为j的物品放入背包
转移方程:
F[i,j]=max\left\{\begin{matrix} F[i-1,j] \;\; 不选择第\;i\;个物品 & \\ F[i-1,j-V_{i}]+W_{i} \;\; 选择第\;i\;个物品& \end{matrix}\right.
边界:F[0,0]=0
目标:max\left \{F[n][j]\right \},其中1\leq j \leq m
时间复杂度:O(nm)
根据上面对于01背包循环的推论,只要将原先程序中的j的循环顺序改为正序,就对应了每个物品可以使用无限次的情况。
代码如下

int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= m; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++)
    ans = max(ans, f[j]);

多重背包

将每种物品拆成C[i]个,类比01背包考虑,状态转移方程略。
代码如下

unsigned int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= c[i]; j++)
        for (int k = m; k >= v[i]; k--)
            f[k] = max(f[k], f[k - v[i]] + w[i]);
int ans = 0;
for (int i = 0; i <= m; i++)
    ans = max(ans, f[i]);

时间复杂度:O(m\sum_{i=1}^{n}C_{i})
考虑优化时间复杂度
优化方法1 对于每种物品进行二进制拆分,将每种物品拆成O(logC_{i})个。
优化方法2 单调队列(详见单调队列优化DP)

分组背包

问题描述:n组物品,第i组里有C_{i}个物品,每个物品有各自的体积和价值,现在每组物品中最多选择一个物品,在总体积不超过m的情况下,令价值和尽量大。
状态表示:F[i,j]表示从前i组物品中选出总体积为j的物品放入背包
转移方程:
F[i,j]=max\left\{\begin{matrix} F[i-1,j] \;\; 不选择第\;i\;组的物品 & \\ max \left \{F[i-1,j-V_{i,k}]+W_{i,k}\right \} \;\; 选择第\;i\;组的某个物品\;k& \end{matrix}\right.
边界:F[0,0]=0
目标:max\left \{F[n][j]\right \},其中1\leq j \leq m
时间复杂度:O(m\sum_{i=1}^{n}C_{i})
考虑优化空间复杂度
和01背包一样,由于每组只选最多一个物品,所以省略掉F数组的第一维
注意:
1 需令第二重倒序循环.
2 每一组内的c[i]个物品的循环k要放在循环j的内层,因为i是阶段,i和j共同构成状态,k是决策,即第i组内用哪个物品,三者顺序不能错乱。
3 分组背包是很多树形DP的基本模型。
代码如下

memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
        for (int k = 1; k <= c[i]; k++)
            if (j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

例题

5201 数字组合
01背包
状态表示:F[j]表示当外层循环到第i个数时,和为j的方案数
转移方程:
F[j]=F[j]+F[j-a[i]]
边界:F[0]=1
目标:F[m]
时间复杂度:O(nm)
空间复杂度:O(nm)
代码如下

/*

*/
#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=10000+5;
const int INF=0x3f3f3f3f;
int f[maxm],n,m,a[maxn];
int main() {
    ios::sync_with_stdio(false);
//  freopen("数字组合.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--) f[j]+=f[j-a[i]];
    cout<<f[m];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

5202 自然数拆分Lunatic版
完全背包
状态表示:F[j]表示当外层循环到第i个数时,和为j的方案数
转移方程:
F[j]=F[j]+F[j-i]
边界:F[0]=1
目标:F[m]
时间复杂度:O(nm)
空间复杂度:O(nm)
代码如下

/*

*/
#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=4000+5;
const ll mod=2147483648;
const int INF=0x3f3f3f3f;
ll f[maxn],n;
int main() {
    ios::sync_with_stdio(false);
//  freopen("自然数拆分Lunatic版.in","r",stdin);
    f[0]=1;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++) f[j]=(f[j]+f[j-i])%mod;
    if(f[n]!=0) cout<<f[n]-1;
    else cout<<mod-1;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1015 Jury Compromise
01背包
状态表示:F[j,k]表示当外层循环到i时,选出了j个人,辩方总分和控方总分差为k时,双方总分的最大值。
转移方程:
F[j]=max\left \{F[j,k],F[j-1,k-(a[i]-b[i])]+a[i]+b[i]\right \}
边界:F[0,0]=0
目标:F[m,k],满足|k|尽量小,|k|相同时,F[m,k]尽量大
时间复杂度:O(20nm^{2})
注意:
1 j一维要倒序循环,满足每个候选人只能选择一次。
2 path[i,j,k]表示F[j,k]取得最优值时的候选人方案,输出方案时,从F[j,k]不断向F[j-1,k-(a[D[j,k]]-b[D[j,k]])]递归,一直到达F[0,0],递归过程中的所有path[i,j,k]就是答案。注意虽然背包DP中的F数组可以省略第一维,但是path数组为了保存方案,必须要加上第一维。
3 F[j-1,k-(a[i]-b[i])]中k-(a[i]-b[i])可能出现负数,导致数组下标越界,所以需要统一进行数组下标平移,详见代码中的zero常量。
代码如下

/*

*/
#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=200+5;
const int maxm1=20+5;
const int maxm=900+5;
const int zero=450;
const int INF=0x3f3f3f3f;
int n,m,a[maxn],b[maxn],f[maxm1][maxm],path[maxn][maxm1][maxm],kase=0,suma,sumb,c[maxm1];
void find(int x,int y,int z) {
    if(!y) return;
    int temp=path[x][y][z+zero];
    suma+=a[temp];
    sumb+=b[temp];
    c[y]=temp;
    find(temp-1,y-1,z-(a[temp]-b[temp]));
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("Jury Compromise.in","r",stdin);
    while(cin>>n>>m&&n&&m) {
        memset(f,0xcf,sizeof(f));
        memset(path,0,sizeof(path));
        int mx=m*20;
        f[0][zero]=0;
        for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
        for(int i=1; i<=n; i++) {
            for(int j=m; j>=1; j--) {
                for(int k=-mx; k<=mx; k++) {
                    path[i][j][k+zero]=path[i-1][j][k+zero];
                    if((f[j-1][k+zero-(a[i]-b[i])]>=0) && (k-(a[i]-b[i])>=-mx) && (k-(a[i]-b[i])<=mx)) {
                        if(f[j-1][k+zero-(a[i]-b[i])]+a[i]+b[i]>f[j][k+zero]) {
                            f[j][k+zero]=f[j-1][k+zero-(a[i]-b[i])]+a[i]+b[i];
                            path[i][j][k+zero]=i;
                        }
                    }
                }
            }
        }
        int ans=mx;
        for(int i=0; i<=mx; ++i) {
            if(f[m][i+zero]>=0&&f[m][i+zero]>=f[m][-i+zero]) {
                ans=i;
                break;
            }
            if(f[m][-i+zero]>=0) {
                ans=-i;
                break;
            }
        }
//      cout<<ans;
        suma=sumb=0;
        find(n,m,ans);
        sort(c+1,c+m+1);
        cout<<"Jury #"<<++kase<<endl;
        cout<<"Best jury has value "<<suma<<" for prosecution and value "<<sumb<<" for defence: "<<endl;
        for(int i=1; i<=m; i++) cout<<" "<<c[i];
        cout<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1742 Coins
多重背包
状态表示:F[j]表示当外层循环到i时,前i种硬币能否拼成j
转移方程:
F[k]=F[k]|F[k-a[i]]
边界:F[0]=1
目标:\sum_{i=1}^{n} F[i]
时间复杂度:O(m\sum_{i=1}^{n}C_{i})
朴素算法代码如下

bool f[100010];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= c[i]; j++)
        for (int k = m; k >= a[i]; k--)
            f[k] |= f[k - a[i]];
int ans = 0;
for (int i = 1; i <= m; i++)
    ans += f[i];

考虑优化
优化方法1 二进制拆分或单调队列
优化方法2 注意到这里仅关注“可行性”,不关注“最优性”,因此仔细分析DP过程,可以发现,若前i种硬币能够拼成面值j,只有两种可能:
1 前i-1种硬币能够拼成面值j,第i重循环开始前,F[j]=1
2 使用了第i种硬币,因为F[j-a[i]]=1,所以推出F[j]=1
于是考虑贪心:设used[j]表示F[j]在阶段i时为1至少需要用多少枚第i种硬币,并且尽量选择第一种情况。具体地说,若F[j-a[i]]=1时,F[j]已经为1,则不进行DP,否则进行转移F[j]|=F[j-a[i]],同时令used[j]=used[j-a[i]]+1
时间复杂度:O(nm)
代码如下

/*

*/
#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=100000+5;
const int INF=0x3f3f3f3f;
int n,m,c[maxn],f[maxm],used[maxm],v[maxn],ans; 
int main() {
    ios::sync_with_stdio(false);
//  freopen("Coins.in","r",stdin);
    while(cin>>n>>m&&n&&m){
        for(int i=1;i<=n;i++) cin>>v[i];
        for(int i=1;i<=n;i++) cin>>c[i];
        memset(f,0,sizeof(f));
        ans=0;
        f[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++) used[j]=0;
            for(int j=v[i];j<=m;j++){
                   //贪心策略        //多重背包
                if(!f[j]&&f[j-v[i]]&&used[j-v[i]]<c[i]){
                    f[j]=1;
                    used[j]=used[j-v[i]]+1;
                }
            }
        }
        for(int i=1;i<=m;i++) if(f[i]) ans++;
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,222评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,455评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,720评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,568评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,696评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,879评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,028评论 3 409
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,773评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,220评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,550评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,697评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,360评论 4 332
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,002评论 3 315
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,782评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,010评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,433评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,587评论 2 350

推荐阅读更多精彩内容

  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,270评论 0 18
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,339评论 0 2
  • "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些阅读 2,028评论 0 2
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,632评论 0 89
  • 今天下班去半道等我们家的老江同学,她在广告公司上班,熬夜加班,再正常不过的事情。 以前我还开玩笑说,你们怎么一直在...
    中医二羊阅读 614评论 2 7