奇迹之流WonderfloW

Nothing Replaces Hard Work!

几种简单类型的动态规划

| Comments

今天又被鱼头拉着校验集训队的书,正好看了一下动态规划(DP)这块,顺便总结一下。发现几道POJ上的例题正好是自己没有做过的,正好拿来试试手,写写题解。

线性动态规划: 1、最长递增(减)子序列:给出一个数列,求最长不下降(上升)子序列的长度。poj2533 这个经典的DP问题有两种解法,复杂度分别为O(n2)和O(nlogn)。

O(n2)的算法比较容易理解,就是用dp[i]表示数列到i位置的最长递增(减)子序列的长度。 第一重循环自然就是枚举i的位置,第二重循环就是从0到i-1,选择一个数字比num[i]小(大)的数的dp值加1,看能否更新dp[i]。 以最长递增子序列为例,就是dp[i] = max(dp[j]+1),(j=0..i-1,且num[j] < num[i])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int n,k,c,ans[1100],maxx,i,j,data[1100];
int main(){
  cin>>n;
  for(i=0;i<n;i++)cin>>data[i];
  ans[0]=1;
  for(i=1;i<n;i++){
      ans[i]=1;
      for(j=0;j<i;j++){
          if(data[j]<data[i] && ans[j]+1>ans[i])
              ans[i] = ans[j] + 1;
      }
  }
  maxx=1;
  for(i=0;i<n;i++)if(ans[i]>maxx)maxx=ans[i];
  cout<<maxx;
}

O(nlogn)的算法其实就是针对O(n2)算法中的第二重循环进行优化,还是以最长递增子序列为例,我们维护一个待选序列ls,这个序列满足ls[i]中存放的就是最长递增子序列为长度i的数列中最大的一个元素。换句话说,到最后,ls数组有多长,最长递增子序列就有多长。 然后我们会发现,ls数组本身就是一组符合条件的最长递增子序列的解,里面的数本身就是有序的,然后更新的时候,我们就可以用到二分查找来进行优化了。 一开始的时候,ls数组长度为0,数字自动填充到ls数组中的第一个位置,长度变为1,然后后面每来一个数,都用二分搜索,找到ls数组中比当前插入值大的最小一个数的位置,然后替换它,如果找不到(即当前要插入的值是最大的),自然就是添加到ls数组末尾,使数组长度增加。 因为我是按照原始数组的顺序进行DP的,那么我当前要插入的值要找到在最终答案里的位置,由于是最长递增序列,那么我前面的数一定比我小,所以我插入的位置一定就是恰好所有前面的数都比我小的位置,替换掉的就是跟我有相同递增长度的那个值,但是我比那个数小,更有前途与后面的数构成更长的递增子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
////二分查找优化 nlogn
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 1005
int f[MAX];
int i,j,ans,n;
int left,right,x,mid;
int main(){
    scanf("%d",&n);
    ans=0;
    for (i=1; i<=n ; i++){
        scanf("%d",&x);
        left=1;
        right=ans;
        while (left<right){
            mid=(left+right)/2;
            if (f[mid]<x) left=mid+1;
            else right=mid;
        }
        if (left>=right&&x>f[ans]||ans==0){
            ans++;
            f[ans]=x;
        }
        else if (x<f[left]){
            f[left]=x;
        }
    }
    printf("%d\n",ans);
    return 0;
}

2、最长公共子序列:求两个字符串的最长公共子序列的长度。 poj1458

这个dp的算法也很经典,在算法导论上有详细的描述。 我们构建一个二维数组dp[N][N],dp[i][j]用来表示串A的第i位为止和串B到第j位为止所拥有的最长公共子序列的长度。 如果stra[i]和strb[j]相等的话,那么显然dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1),否则就是从dp[i][j-1]和dp[i-1][j]中取个较大的值。(从dp[i-1][j-1]递推过来的情况已经包含在dp[i][j-1]和dp[i-1][j]里面了。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;
char a[300],b[300];
int c[300][300];
int lcs_length()
{
  int cnt=0;
  int m=strlen(a);
  int n=strlen(b);
  int i,j;
  for(i=1;i<m;i++)c[i][0]=0;
  for(j=0;j<n;j++)c[0][j]=0;
  for(i=0;i<m;i++)
      for(j=0;j<n;j++)
      {
          if(a[i]==b[j])c[i+1][j+1]=c[i][j]+1;
          else if(c[i][j+1]>=c[i+1][j])
              c[i+1][j+1]=c[i][j+1];
          else c[i+1][j+1]=c[i+1][j];
      }
      return c[m][n];
}

int main()
{
  while(scanf("%s%s",a,b)!=EOF)
  {
      printf("%d\n",lcs_length());
  }
}

3、最大子段和:从一个有N个浮点数的一维数组中找出一段连续的元素,使其构成的子数组之和最大。 这个题也许算不上一个标准的动态规划经典题目,但是在《编程珠玑》和《编程之美》两本书上,均有大篇幅的笔墨讲解,所以我认为它是有价值的。 O(n2)的暴力解法大家应该都很容易想到,我就不说了。 然后我们自然要想着优化,那么分治的思想就可以让我们联想到O(nlogn)的算法。 (A[0],..,A[n-1])的最大子段和无非包含在3种情况内,由数组的左半部分组成,由数组的右半部分组成,横跨数组左右两边。 对于前两种情况,就是递归解决。对于第三种情况,因为它一定包含A数组最中间,即A[n/2-1]这个数,那么我们只要从这个数向左右两边伸展开去,找个最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
float maxsum(float *A,int l,int r){
  if(l>r)return 0;
  if(l==r)return max(0,A[l]);
  int mid = (l+r)/2;
  double sum;
  double lmax = sum = 0;
  for(int i=mid;i>=l;i--){
      sum+=A[i];
      lmax = max(lmax,sum);
  }
  double rmax = sum = 0;
  for(int i=mid+1;i<=r;i++){
      sum+=A[i];
      rmax = max(rmax,sum);
  }
  return max(lmax+rmax,maxsum(l,mid),maxsum(mid+1,r));
}

实际上还有O(N)的算法,而它也是最简单,只要扫一遍数组即可。从左向右,计算当前的和,如果当前的和一直是正的,那么不管是大是小,我后面的最大字段和加上当前这一段非负的,也没有亏,还是最大字段和。如果当前的和出现了负值,那么当前值就置为0。肯定是不要了啊,最次我什么都不选,也是0.就这样一路扫到最后即可。

1
2
3
4
5
6
7
8
9
10
11
float maxsum(float *A,int n){
  double nstart = A[n-1];
  double nall = A[n-1];
  for(int i=n-2;i>=0;i--){
      if(nstart<0)nstart = 0;
      nstart+=A[i];
      if(nstart>nall)
          nall = nstart;
  }
  return nall;
}

4、背包问题:这个看一下背包九讲吧。

树形动态规划 5、POJ 1463 有若干结点,结点之间有路相连,构成树形结构,如果在一个结点上放置一个士兵,与这个结点相连的路就可以被监视,现在要监视所有的路,问至少要多少士兵。

这个是最简单的树形DP,可以理解为DFS遍历整棵树的同时,记录下我当前点放士兵和不放士兵所能达到的最优情况。因为如果我树确定了根节点,子树一个个下去是不存在后效性的问题的,而且子树本身就是一个子结构,所以很容易联想到DP来解决这一类问题。 开个DP[N][2]的数组,dp[i][0]表示,以i节点为子树的根,i节点不放士兵,最少总共要放多少士兵。dp[i][1]就是i节点放士兵最少要在子树中放多少士兵。 显然如果一个子树的根节点不放士兵的话,那么与其相连的所有子树的根节点一定要放士兵,否则那条边就没有士兵看管了。 反之,如果一个子树的根节点放士兵的话,那么与其相连的所有子树可以选择放士兵,或者不放士兵。 理解了这个,记忆化的过程,或者说状态转移的过程就一目了然了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>edge[1510];
int dp[1510][2];
bool vis[1510];

int dfs(int ind,int status){
  if(dp[ind][status]!=-1)return dp[ind][status];
  vis[ind] = true;
  dp[ind][0] = 0;
  dp[ind][1] = 1;
  for(int i=0;i<edge[ind].size();i++){
      int v = edge[ind][i];
      if(vis[v])continue;
      dp[ind][0] += dfs(v,1);
      dp[ind][1] += min(dfs(v,1),dfs(v,0));
  }
  return dp[ind][status];

}

int main(){
  int ind,num,t;
  int n;
  while(scanf("%d",&n)!=EOF){
      for(int i=0;i<=n;i++)edge[i].clear();
      for(int i=0;i<n;i++){
          scanf("%d:(%d)",&ind,&num);
          for(int j=0;j<num;j++){
              scanf("%d",&t);
              edge[ind].push_back(t);
              edge[t].push_back(ind);
          }
      }
      memset(dp,-1,sizeof(dp));
      memset(vis,0,sizeof(vis));
      dfs(0,1);
      printf("%d\n",min(dp[0][0],dp[0][1]));
  }
  return 0;
}

概率动态规划

6、poj3071 一场足球淘汰赛有2ˆn 支队伍参加,编号为1,2,.,2n,按队伍编号进行比赛,每轮比赛的胜者再与对应比赛的胜者进行比赛,输掉一场比赛该队伍即被淘汰。现在给出每支队伍与其他所有队伍进行比赛胜利的概率,求最可能成为冠军的队伍编号。POJ上与其基本相同的题:POJ2261 阿森说,概率DP根本不是DP,因为涉及到了概率,根本不存在最优的情况。我深以为然。 就是按公式算起来嘛!用到DP的地方估计也就是算的过程,一步步递推很像DP的写法而已。 那么这题其实也是这样的,按照1号先和2号打,3号先和4号打.. 然后第二轮,1号和3、4中的胜者打(由于是概率,所以3、4都有可能胜,所以就是和3、4都计算),以此类推。 那么为什么要把这个题目放在这里呢? 价值就在于中间计算的过程。我们可以想象一下,其实淘汰赛的比赛过程就是一颗满二叉树,而满二叉树有这样一个性质,父亲节点相同的两个左右子树,其序号映射到二进制位上比较的话,他们只相差1位。第n轮比赛其实就是子树向上去的第n层,然后我要取的就是该层的兄弟节点子树包含的所有最底层的节点。怎么找到这些点呢?操作很简单,2n~2n+1之间所有的点与当前点异或一下,就出来啦。(实际上就是自底向上第n层那个点相反的变化了一下而已。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
double dp[16][512];
double m[512][512];
int len;
int main(){
  int n;
  while(scanf("%d",&n)&&n!=-1){
      len = (1<<n);
      for(int i=0;i<len;i++){
          for(int j=0;j<len;j++){
              scanf("%lf",&m[i][j]);
          }
          dp[0][i] = 1;
      }
      for(int k=1;k<=n;k++){
          for(int i=0;i<len;i++){
              double sum = 0;
              for(int j=(1<<(k-1));j<(1<<k);j++){
                  sum += dp[k-1][j^i]*m[i][j^i];
              }
              dp[k][i] = dp[k-1][i]*sum;
          }
      }
      int ans = 0;
      for(int i=1;i<len;i++){
          if(dp[n][i]>dp[n][ans]){
              ans = i;
          }
      }
      printf("%d\n",ans+1);
  }
}

状态压缩动态规划

7、这类题目的基本思想就是拿一个数的每个或每两个二进制位表示当前位的状态,然后进行状态转移。我博客上之前写过几个这样题目的解题报告,这里就暂不添加其他题目了。我先前的解题报告:ZOJ1100 Mondriaan’s Dream ZOJ1155 《Triangle War》 hdu4317《Unfair Nim》

插头动态规划

8、这一类的DP其实是以状态压缩DP为基础的,在状态压缩的基础上假设出更多不同的状态(不同的插头),然后进行转移。 国家队2008年陈丹琦的论文《基于连通性状态压缩的动态规划问题》,非常详细的介绍了这一类的DP,大家可以百度或者google搜一下这篇文章。 然后集训队讲报告的时候,关于这一块,我觉得方老师讲解的非常好,在此设立传送门,有兴趣的话可以去读一下方老师的文章,图文并茂很清楚~

几类简单的DP类型大致就是这样了吧,其实DP千变万化,最主要的还是要看出问题的子结构,想清楚里面的状态转移,以及想清楚如何优化。