浅谈动态规划

legenda

什么是动态规划

动态规划(Dynamic Programming)亦如其名，将某个问题分解为相似多个小问题后寻找与原问题关系，通过这种关系返回原问题的解，一般用于求解最优问题。我们将这个子问题成为原问题的一个状态，关系称为状态转移。
入门：在一棵完全二叉树上找到子叶到根的数字和最大值。
对于动态规划中最大的问题，便是找到状态转移方程。也为此人们将一类状态转移方程的问题归结到一起，起一个新的名字，下文对不同种动态规划进行粗略说明。

背包问题

背包问题是指给定一定数量的物品与其价值和背包容量，在不同的情况与条件下如何获得背包内的物品价值最大值。
一般来说，由于贪心导致背包空余部分较小或存放物品不符合条件使得贪心无法解决背包问题，于是乎便引入了动态规划来解决背包问题。

01背包

对于01背包，物品只有两个状态，即放入与未放入。一般来说此类问题会考察放入物品的最大值，但有时题目会另辟蹊径，添加一些奇奇怪怪的条件，如放入的物品数量限制(放入“物品”需要消耗“法力值”)，物品的条件限制(奇数价值与偶数价值物品数量相同…)等。对于此类只需在原问题上添加一些简单的分治算法甚至if语句即可。一般来说其状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])。

完全背包与多重背包浅谈

完全背包即在01背包的基础上将物品数量改为无限，而多重背包在01背包的基础上将物品改为一定量。对于此类问题只需在01背包基础上添加一层for或者改为数位dp即可。当然，一般题目也会有一些条件上的改动，添加一些改动即可。

区间DP

区间DP顾名思义就是对于某个区间，通过dp的方法得到题目所需要的解。此类问题的困难之处一般在于寻找区间的分割点，对于一些好的分割方式，效率能达到2倍以上。但很多情况下还是使用最简单的分割办法：按照题目要求一个个推。一般来说其状态转移方程为dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+f(k,j))。

状压DP

与01背包类似，每个“物品”只有‘0’与‘1’两种状态，只不过此时“物品”间存在某种特殊的联系。需要不断通过状态转移方程与’|‘ ’&‘ ’«‘ ’»'等运算得出题目要求下的解。一般来说其状态转移方程与01背包的状态转移方程略有不同，可能多一个f(i,j)，可能变成dp[i][j][k],也可能加一个val[i-1][j]。

数位DP

数位dp一般是求出在给定区间内，符合一个关于数位的条件的数的个数。一般来说就是简单的dfs+记忆化，但有时会混入一些奇奇怪怪的东西，如dfs条件与记忆化数组冲突(其实这个很常见，毕竟很少有题目能直接套模板)，dp状态使得dfs无法继续但又不是最优解(添加“一些”if语句)，dfs过程中的部分数字使得答案错误(特判)等。因此对于数位dp需要仔细判断题目条件与区间数字特征。

树形DP(树+环)

很简单，树上dp。

其他高级DP

很离谱，看不懂。
随便写一点。

dp与计算几何

一般来说dp[i][j][k]=max(dp[i-1][j][k]+val[a][b][c])对于i,j,k的val，由于计算几何的数据规模较小，大部分情况都预先算出来所有的val并存入数组，后直接调用。

dp与博弈

一般来说4层for起步(2维套2维)。

DP优化

1.单调队列优化
2.斜率优化
3.其他优化(数据结构,记忆化,分治…)

写出来就不错了，还要优化……

legenda

例题：

取自《算法竞赛与入门经典》

最长滑雪路径

题目：在一个R*C的整数矩阵上找到一条高度严格递减的最长路。
解答：用dp[i][j]表示从(i,j)开始的最短路，易得知dp[i][j]=max(1+dp[i1][j1]),当无符合条件的(i1,j1)时，dp[i][j]=1。记忆化搜索即可。
答案：略

切蛋糕(ACM2007,Nanjing)

题目：在一个n*m的网格蛋糕上放有一些樱桃。每次只可沿网格切一刀直线分为两块。要求最后每一块蛋糕上恰好只有一颗樱桃，且切割长度最小。
解答：考虑切好后的每一块蛋糕，对于每一块蛋糕遍历横切与竖切，同时保证每次搜索后切开的两块蛋糕上至少包含一个樱桃。在遍历过程中求出每个子矩阵的樱桃个数，之后进行记忆化搜索所有子矩阵的樱桃个数。此时时间空间复杂度均为O(N³ M³)
代码：

const int maxn=21;
int n,m,k,d[maxn][maxn][maxn][maxn],chery[maxn][maxn][maxn][maxn];
//防止条件错误而卡死
/*void check(int r,int c,int width,int heigh){
    assert(width>=1);
    assert(heigh>=1);
    assert(0<=r&&r<n);
    assert(0<=c&&c<m);
    assert(r+heigh<=n);
    assert(c+width<=m);
}*/
int cr_cnt(int r,int c,int width,int heigh){
    int& ans=chery[r][c][width][heigh];
    if(ans!=-1)return ans;
    if(width>1)return ans=cr_cnt(r,c,1,heigh)+cr_cnt(r,c+1,width-1,heigh);
    return ans=cr_cnt(r,c,1,1)+cr_cnt(r+1,c,1,heigh+1);
}
int dp(int r,int c,cosnt int W,const int H){
    int& ans=d[r][c][W][H];
    if(ans!=-1)return ans;
    if(cr_cnt(r,c,W,H)==1)return ans=0;
    auto updateans=[&](int a){//C++11
        if(ans==-1)ans=a;
        else ans=min(ans,a);
    };
    for(int h=1;h<H;h++){
        if(cr_cnt(r,c,W,h)>=1&&cr_cnt(r+h,c,W,H-h)>=1)
        updateans(H+dp(r,c,W,H-h)+dp(r+h,c,W,H-h));
    }
        for(int w=1;w<W;w++){
        if(cr_cnt(r,c,W,h)>=1&&cr_cnt(r,c+w,W-w,H)>=1)
        updateans(H+dp(r,c,W,H)+dp(r,c+w,W-w,H));
    }
    return ans;
}
int main(){
    for(int case=1,r,c;scanf("%d%d%d",&n,&m,&k)==3;case++){
        memset(d,-1,sizeof(d));
        memset(chery,-1,sizeof(d));
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)chery[i][j][1][1]=0;
        for(int i=0;i<k;i++){cin>>r>>c;chery[r-1][c-1][1][1]=1;}
    printf("%d:%d\n",case,dp(0,0,m,n));
    }
    return 0;
}

保卫

题目：给定一个有n（n≤10000）个结点的无根树。有两种装置A和B，每种都有无限多个。
在某个结点X使用A装置需要C1（C1≤1000）的花费，并且此时与结点X相连的边都被覆盖。
在某个结点X使用B装置需要C2（C2≤1000）的花费，并且此时与结点X相连的边以及与结点X相连的点相连的边都被覆盖。求覆盖所有边的最小花费。
解答：不难想到是树形 DP,考思每个结点的覆盖状态。不妨把n=1作为树根。令 D(u,s)表示以节点u为根的子树，当前覆盖状态为s所需的最小花费。对于结点u,统称其任意孩子为v,任意孙子为vx,u的父亲为p,p的父亲为px,u的任意兄弟结为ux。则s根据边u-v,v-vx,u-p,u-px的覆盖情况分为0，1，2，3四种情况。从下往上进行dfs，根据u的孙子节点的覆盖情况来进行状态转移，最后得出答案min(D(1,0),D(1,1),D(1,2))。
代码：

const int MAXN=10004,INF=INT_MAX;
int N,C1,C2,DP[MAXN][4];
vector<int> G[MAXN];
int min(int a,int b,int c){ return min(min(a,b),c);}
int min(int a,int b,int c,int d){ return min(min(a,b),min(c, d));}
void dfs(int u, int fa){
    int *D=DP[u], U1E=0, minV0=INF;
    memset(D, 0,sizeof(DP[u]));
    for(auto v:G[u]){//C++11
        if(v==fa)continue;   
        dfs(v,u);
        int *DV=DP[v],w=min(DV[0],DV[1],DV[2]);
        D[0]+=min(DV[0],DV[1],DV[2],DV[3]);
        D[1]+=w;//u上面放A
        D[2]+=DV[1];
        D[3]+=w;
        U1E+=w;//u上面不放A的费用
        minV0=min(minV0,DV[0]-w);//DV=0对于费用的增加
    }
    D[0]+=C2,D[1]=min(D[1]+C1,U1E+minV0);
}
int main(){
    int u,v;
    while(scanf("%d%d%d",&N,&C1,&C2)==3&&N){
        for(int i=0,i<=N,i++) G[i].clear();
        for(int i=1,i<N,i++)
            scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
        dfs(1,-1);
        printf("%d\n",min(DP[1][0],DP[1][1],DP[1][2]));
    }
    return 0;
}

圆和多边形

题目：给你一个圆和圆周上的n（3≤n≤40）个不同点。请选择其中的m（3≤m≤n）个，按照在圆周上的顺序连成一个m边形，使得它的面积最大。
解答：易知D[i][j][k]=D[i][x][k-1]+S[i][x][j]。
代码：

const int MAXN=50;
const double PI=acos(-1);//pi的高精度
double dist(double p1, double p2){
    double a=fabs(p2-p1); //assert(a<1);
    if (a>0.5)a=1-a;
    return 2*sin(a*PI);
}
double calArea(double a,double b,double c){
    double x=(a+b+c)/2;
    return sqrt(x*(x-a)*(x-b)*(x-c));
}

int n,m;
double P[MAXN],d[MAXN][MAXN],area[MAXN][MAXN][MAXN],DP[MAXN][MAXN][MAXN];
double dp(){
    memset(DP,0,sizeof(DP));
    for(int k=3;k<=mk++)
        for(int i=0;i<n;i++)for(int x=i+1;x<n,x++)for(int j=x+1;j<n;j++)
            DP[i][j][k]=max(DP[i][j][k],DP[i][x][k-1]+area[i][x][j]);
    double ans=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)ans=max(ans,DP[i][j][m]);
    return ans;
}

int main() {
    while (scanf("%d%d",&n,&m) ==2&&n) {
        for(int i=0;i<n;i++)scanf("%lf",&(P[i]));
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) d[i][j] = d[j][i] = dist(P[i], P[j]);
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=j+1;k<n;k++) { 
            area[i][j][k]=area[i][k][j]= area[j][i][k]=area[j][k][i]= area[k][i][j]=area[k][j][i]= calArea(d[i][j], d[j][k], d[k][i]);
        }
        printf("%.6lf\n",dp());
    }
    return 0;
}

打棒球

题目：你经营着一支棒球队。在接下来的g+10天中会有g（3≤g≤200）场比赛，其中每天最多一场比赛。你已经分析出你的n（5≤n≤100）个投手中每个人对阵所有m（3≤m≤30）个对手的胜率（一个n*m矩阵），要求给出作战计划（即每天使用哪个投手），使得总获胜场数的期望值最大。注意，一个投手在上场一次后至少要休息4天。
解答：每个投手上场一次至少休息4天，对于每场比赛来说，胜率最高的5个投手不可能4天都参加比赛（每天最多一场，每场只需1个投手），所以至少有1个休息够了，可以只考虑胜率最高的5个人。
令DP(i,p0,pl,p2,p3)表示第i天，选择对阵当天对手胜率排名第p0的对手商场，且第i-x天选择对应排名第px的上场，前i天所能得到的最大得分。其中px=0则表示当天无人上场。
状态转移时,首先要保证第i天选择的投手不能和前面4天重复，然后对于每i天来说，有两种情况：
(1)没有比赛:则 D(i,0,pl,p2,p3)=max(D(i-1,p1,p2,p3,p4)，其中0≤p4≤p5。
(2)有比赛:则D(i,p0,pl,p2,p3) =max((D(i-1,p1,p2,p3,p4)+p)，对p0进行决策,p是对当天对手胜率排名p0的选手的胜率。
时间复杂度为O(g*5⁵),因为五维数组占用空间较大,需使用滚动数组这样空间复杂度就是常数O(2*6⁴)。
代码：

const int MAXN=104, MAXG=200+10+4;
struct WinP{
    int p,pit;
    WinP():p(0),pit(0){}
    bool operator<(const WinP& s)const{return p>s.p;}
};
WinP winps[MAXN][MAXN];
int N,M,numG,G[MAXG],DP[2][6][6][6][6];
inline int getPi(int op,int i){return winps[op][i].pit;}
double solve(){
    memset(DP,0,sizeof(DP));
    int ans=0,cur=0;
    for(int i=1;i<=numG;i++) {
        int prev=cur,now=1-cur;
        cur=1-cur;
        memset(DP[now],0,sizeof(DP[now]));
        int op=G[i];
        if (op==0){
            for(int p1=0;p1<=5;p1++)for(int p2=0;p2<=5;p2++)for(int p3=0;p3<=5;p3++)for(int p4=0;p4<=5;p4++) {
                int& d=DP[now][0][p1][p2][p3]; 
                d=max(d,DP[prev][p1][p2][p3][p4]); 
                ans=max(d,ans);
            }
            continue;
        }
        for(int p0=1;p0<=5;p0++){
            int opi = getPi(op, p0);
            for(int p1=0;p1<=5;p1++){
                if (i > 1 && getPi(G[i-1],p1)==opi) continue;
                for(int p2=0;p2<=5;p2++){
                    if (i > 2 && getPi(G[i-2],p2)==opi) continue;
                    for(int p3=0;p3<=5;p3++){
                        if (i > 3 && getPi(G[i-3],p3)==opi) continue;
                        for(int p4=0;p4<=5;p4++){
                            if (i > 4 && getPi(G[i-4],p4)==opi) continue;
                            int& d=DP[now][p0][p1][p2][p3];
                            d=max(d,DP[prev][p1][p2][p3][p4]+winps[op][p0].p);
                            ans=max(d,ans);
        }}}}}}
    double d=ans*.01;
    return d;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&N,&M,&numG);numG+=10;
        for(int i=1;i<=M;i++){
            for(int j=1;j<=N;j++){
                scanf("%d", &(winps[i][j].p));
                winps[i][j].pit=j;
            }
            sort(winps[i]+1, winps[i]+N+1);
        }
        G[0]=0;
        for(int i=1;i<=numG;i++)scanf("%d",&(G[i]));
        double ans=solve();
        printf("%.2lf\n", ans);
    }
    return 0;
}