dp 专题-白红宇

dp 专题

阅读量：6982 次

发布时间：2019-06-27

本文共 16273 字，大约阅读时间需要 54 分钟。

最近几天一直在做DP，又学习了两种方法：斜率优化，单调队列优化。

hdu 2577 How to Type

打印字母，很经典的一类dp，用二维数组表示:

dp[i][0]表示打印完第i个字符，键盘上的大写锁定键是关闭着的。

dp[i][1]表示打印完第i个字符，键盘上的大写锁定键的打开着的。

那么根据第i个字母的大小写就很容易写出前后的转化关系。

code:

View Code

1 # include
      
         2 # include
       
          3 int min(int a,int b)  4 {
     5     return a
        
         ='a' && str[i]<='z') 21             {
    22                 dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+2); 23                 dp[i][1]=min(dp[i-1][1]+2,dp[i-1][0]+2); 24             } 25             else 26             {
    27                 dp[i][0]=min(dp[i-1][0]+2,dp[i-1][1]+2); 28                 dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+1); 29             } 30         } 31         printf("%d\n",min(dp[i-1][0],dp[i-1][1]+1)); 32     } 33     return 0; 34 }

hdu 1513 Palindrome

求把一个字符串转化成回文需要最少的操作次数。

把这个字符串反过来写一遍，然后这两个字符串求最长公共子序列。

最后字符串长度-公共子序列长度就是最少的操作数。

长度比较大，需要用到滚动数组。

View Code

1 # include
      
         2 # include
       
          3 # define N 5005  4 int max(int a,int b)  5 {
     6     return a>b?a:b;  7 }  8 int main()  9 {
    10     int i,j,n,dp[2][N]; 11     char str1[N],str2[N]; 12     while(scanf("%d",&n)!=EOF) 13     {
    14         scanf("%s",str1+1); 15         for(i=n;i>=1;i--) 16             str2[i]=str1[n-i+1]; 17         memset(dp,0,sizeof(dp)); 18         for(i=1;i<=n;i++) 19             for(j=1;j<=n;j++) 20             {
    21                 if(str1[i]==str2[j]) 22                     dp[i%2][j]=dp[(i-1)%2][j-1]+1; 23                 else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]); 24             } 25             printf("%d\n",n-dp[n%2][n]); 26     } 27     return 0; 28 }

hdu 3351 Seinfeld

字符串匹配问题，此题比较简单。

在读入的过程中，把相匹配的删除，最后会存在下面三种形态：

1. }}}...

2. {

{

{...

3. }}}...{

{

{...

对于每种形态就很容易求了。

View Code

1 # include
      
         2 # include
       
          3 # define N 2005  4 int main()  5 {
     6     int i,n,ncase=0,a,b,ans,top;  7     char str[N],map[N];  8     while(scanf("%s",str+1)!=EOF)  9     {
    10         ncase++; 11         if(str[1]=='-') break; 12         n=strlen(str); 13         top=0; 14         for(i=1;i

hdu 1978 How many ways

简单DP，从左到右，从上到下依次访问每一个位置。

从该位置(x0,y0)能到达的所有位置(xi,yi)，

dp[xi][yi]+=dp[x0][y0];

View Code

1 # include
      
         2 # include
       
          3 # define N 105  4 int map[N][N],dp[N][N];  5 int main()  6 {
     7     int i,j,n,m,ncase,i1,j1;  8     scanf("%d",&ncase);  9     while(ncase--) 10     {
    11         scanf("%d%d",&n,&m); 12         for(i=1;i<=n;i++) 13             for(j=1;j<=m;j++) 14                 scanf("%d",&map[i][j]); 15         memset(dp,0,sizeof(dp)); 16         dp[1][1]=1; 17         for(i=1;i<=n;i++) 18             for(j=1;j<=m;j++) 19             {
    20                 for(i1=i; i1-i<=map[i][j]&&i1<=n;i1++) 21                 {
    22                     for(j1=j;j1-j+i1-i<=map[i][j]&&j1<=m;j1++) 23                     {
    24                         if(i1==i &&j1==j) continue; 25                         dp[i1][j1]+=dp[i][j]; 26                         dp[i1][j1]%=10000; 27                     } 28                 } 29             } 30         printf("%d\n",dp[n][m]); 31     } 32     return 0; 33 }

hdu 1506 Largest Rectangle in a Histogram

求能够成的最大矩形的面积。

遍历每个点，向两边延展，遇到比该点低的停止。

求出宽度，宽度*该点的高度就是在该点时的最大面积。

需要用两个数组记录，否则会超时。

View Code

1 # include
      
         2 # include
       
          3 # define N 100005  4 int l[N],r[N];  5 __int64 a[N],Max;  6 __int64 max(__int64 a,__int64 b)  7 {
     8     return a>b?a:b;  9 } 10 int main() 11 {
    12     int i,n; 13     while(scanf("%d",&n)!=EOF && n) 14     {
    15         for(i=1;i<=n;i++) 16         {
    17             scanf("%I64d",&a[i]); 18             l[i]=r[i]=i; 19         } 20         Max=0; 21         a[n+1]=a[0]=-1; 22         for(i=1;i<=n;i++) 23         {
    24             while(a[l[i]-1]>=a[i]) 25                 l[i]=l[l[i]-1]; 26         } 27         for(i=n;i>=1;i--) 28         {
    29             while(a[r[i]+1]>=a[i]) 30                 r[i]=r[r[i]+1]; 31         } 32         for(i=1;i<=n;i++) 33         {
    34             Max=max((r[i]-l[i]+1)*a[i],Max); 35         } 36         printf("%I64d\n",Max); 37     } 38     return 0; 39 }

hdu 1505 City Game

上题的加强版，加一个数组记录就可以了。

View Code

1 # include
      
         2 # include
       
          3 # define N 1005  4 int map[N][N],dp[N][N],s[N],Max,l[N],r[N];  5 int max(int a,int b)  6 {
     7     return a>b?a:b;  8 }  9 int main() 10 {
    11     int i,j,n,m,ncase; 12     char ch[3]; 13     scanf("%d",&ncase); 14     while(ncase--) 15     {
    16         scanf("%d%d",&n,&m); 17         memset(dp,0,sizeof(dp)); 18         for(i=1;i<=n;i++) 19         {
    20             for(j=1;j<=m;j++) 21             {
    22                 scanf("%s",ch); 23                 if(ch[0]=='R') map[i][j]=0; 24                 else map[i][j]=1; 25             } 26         } 27         Max=0; 28         for(i=1;i<=n;i++) 29         {
    30             for(j=1;j<=m;j++) 31             {
    32                 if(map[i][j]) dp[i][j]=dp[i-1][j]+1; 33                 s[j]=dp[i][j]; 34                 l[j]=r[j]=j; 35             } 36             s[0]=-1; 37             s[m+1]=-1; 38             for(j=1;j<=n;j++) 39             {
    40                 while(s[l[j]-1]>=s[j]) 41                     l[j]=l[l[j]-1]; 42             } 43             for(j=n;j>=1;j--) 44             {
    45                 while(s[r[j]+1]>=s[j]) 46                     r[j]=r[r[j]+1]; 47             } 48             for(j=1;j<=n;j++) 49                 Max=max(Max,(r[j]-l[j]+1)*s[j]); 50         } 51         printf("%d\n",Max*3); 52     } 53     return 0; 54 }

hdu 2870 Largest Submatrix

上题的加强版。

三种情况。

全部变为a,全部为b，全部为c,分别求最大。

View Code

1 # include
      
          2 # include
       
           3 # define N 1005   4 char map[N][N];   5 int dp[N][N][3],Max,s[N],l[N],r[N];   6 int max(int a,int b)   7 {
      8     return a>b?a:b;   9 }  10 int is1(char ch)  11 {
     12     if(ch=='a'||ch=='w'||ch=='y'||ch=='z') return 1;  13     return 0;  14 }  15 int is2(char ch)  16 {
     17     if(ch=='b'||ch=='w'||ch=='x'||ch=='z') return 1;  18     return 0;  19 }  20 int is3(char ch)  21 {
     22     if(ch=='c'||ch=='x'||ch=='y'||ch=='z') return 1;  23     return 0;  24 }  25 int main()  26 {
     27     int i,j,n,m;  28     while(scanf("%d%d",&n,&m)!=EOF)  29     {
     30         for(i=1;i<=n;i++)  31         {
     32             scanf("%s",map[i]);  33             for(j=m-1;j>=0;j--)  34                 map[i][j+1]=map[i][j];  35         }  36         memset(dp,0,sizeof(dp));  37         Max=0;  38         for(i=1;i<=n;i++)  39         {
     40             for(j=1;j<=m;j++)  41             {
     42                 if(is1(map[i][j])) dp[i][j][0]=dp[i-1][j][0]+1;  43                 if(is2(map[i][j])) dp[i][j][1]=dp[i-1][j][1]+1;  44                 if(is3(map[i][j])) dp[i][j][2]=dp[i-1][j][2]+1;  45             }  46             for(j=1;j<=m;j++)  47             {
     48                 s[j]=dp[i][j][0];  49                 l[j]=r[j]=j;  50             }  51             s[0]=s[m+1]=-1;  52             for(j=1;j<=m;j++)  53             {
     54                 while(s[l[j]-1]>=s[j])  55                     l[j]=l[l[j]-1];  56             }  57             for(j=m;j>=1;j--)  58             {
     59                 while(s[r[j]+1]>=s[j])  60                     r[j]=r[r[j]+1];  61             }  62             for(j=1;j<=m;j++)  63                 Max=max(Max,(r[j]-l[j]+1)*s[j]);  64  65             for(j=1;j<=m;j++)  66             {
     67                 s[j]=dp[i][j][1];  68                 l[j]=r[j]=j;  69             }  70             s[0]=s[m+1]=-1;  71             for(j=1;j<=m;j++)  72             {
     73                 while(s[l[j]-1]>=s[j])  74                     l[j]=l[l[j]-1];  75             }  76             for(j=m;j>=1;j--)  77             {
     78                 while(s[r[j]+1]>=s[j])  79                     r[j]=r[r[j]+1];  80             }  81             for(j=1;j<=m;j++)  82                 Max=max(Max,(r[j]-l[j]+1)*s[j]);  83             for(j=1;j<=m;j++)  84             {
     85                 s[j]=dp[i][j][2];  86                 l[j]=r[j]=j;  87             }  88             s[0]=s[m+1]=-1;  89             for(j=1;j<=m;j++)  90             {
     91                 while(s[l[j]-1]>=s[j])  92                     l[j]=l[l[j]-1];  93             }  94             for(j=m;j>=1;j--)  95             {
     96                 while(s[r[j]+1]>=s[j])  97                     r[j]=r[r[j]+1];  98             }  99             for(j=1;j<=m;j++) 100                 Max=max(Max,(r[j]-l[j]+1)*s[j]); 101         } 102         printf("%d\n",Max); 103     } 104     return 0; 105 }

hdu 2686 Matrix

多线程DP。

题意：从左上角走到右下角，再从右下角走到左上角，保证所走得两条路线不相交，问最后能得到的最少数（每走到一个点上就加上该点的值）

思路：可以转化为同时从左上角出发的两条线。

枚举步数：dp(k,x1,y1,x2,y2)=max[dp(k-1,x1-1,y1,x2-1,y2),dp(k-1,x1-1,y1,x2,y2-1),dp(k-1,x1,y1-1,x2-1,y2),dp(k-1,x1,y1-1,x2,y2-1)];

需保证x1!=x2&&y1!=y2;

因为坐标(x1,y1)与步数k之间有一个关系，只要知道k与x1就能求出y1，所以可以转化为一个三维的。

View Code

1 # include
      
         2 # include
       
          3 # define N 31  4 int dp[2*N][N][N],a[3],b[3],map[N][N];  5 int max(int a,int b)  6 {
     7     return a>b?a:b;  8 }  9 int main() 10 {
    11     int i,j,n,x1,x2,i1,i2,k; 12     while(scanf("%d",&n)!=EOF) 13     {
    14         for(i=0;i

hdu 3392 Pie

输入n个男生，m个女生的身高。

把人数较少的一方和另外一方匹配完，求最少的差值。

分别把男女的身高排序。人数较少的一方的每个人可以匹配abs（m-n+1）个人。

因为|m-n|<=100 所以一个人最多匹配100人。

之后用二维滚动数组就可以了。

View Code

1 # include
      
         2 # include
       
          3 # include
        
           4 # include
         
            5 # define N 10005  6 double dp[2][105];  7 int cmp(const void *a,const void *b)  8 {
     9     return *(double *)a > *(double *)b ? 1 : -1; 10 } 11 double min(double a,double b) 12 {
    13     return a

hdu 1422 重温世界杯

因为可以构成一个环，所以可以把前面的n-1复制到后面

s[n+1]=s[1];s[n+2]=s[2]......

之后就很简单了，在保证sum>=0的情况下求最多能访问多少个城市。

View Code

1 # include
      
         2 # include
       
          3 # define N 100005  4 int s[2*N];  5 int max(int a,int b)  6 {
     7     return a>b?a:b;  8 }  9 int main() 10 {
    11     int i,j,n,end,count,Max,a,b; 12     while(scanf("%d",&n)!=EOF) 13     {
    14         for(i=1;i<=n;i++) 15         {
    16             scanf("%d%d",&a,&b); 17             s[i]=a-b; 18         } 19         for(i=n+1;i<=2*n-1;i++) 20             s[i]=s[i-n]; 21         end=0; 22         count=0; 23         Max=0; 24         for(i=1;i<=2*n-1;i++) 25         {
    26             if(end+s[i]>=0) {count++;end+=s[i];} 27             else 28             {
    29                 Max=max(Max,count); 30                 if(Max>=n) break; 31                 count=0; 32                 end=0; 33             } 34         } 35         Max=max(Max,count); 36         if(Max>=n) Max=n; 37         printf("%d\n",Max); 38     } 39     return 0; 40 }

hdu 2830 Matrix Swapping II

也是求最大矩阵的，只不过可以相互交换任意两列。

访问每一行时，求出每个点的高度，然后排序，以该点为高时的宽度就很容易看出来，面积取最大的就可以了。

View Code

1 # include
      
         2 # include
       
          3 # include
        
           4 # define N 1005  5 char map[N][N];  6 int dp[N][N],s[N];  7 int cmp(const void *a,const void *b)  8 {
     9     return *(int *)a - *(int *)b; 10 } 11 int max(int a,int b) 12 {
    13     return a>b?a:b; 14 } 15 int main() 16 {
    17     int i,j,n,m,k,Max; 18     while(scanf("%d%d",&n,&m)!=EOF) 19     {
    20         for(i=1;i<=n;i++) 21         {
    22             scanf("%s",&map[i]); 23             for(j=m-1;j>=0;j--) 24                 map[i][j+1]=map[i][j]; 25         } 26         memset(dp,0,sizeof(dp)); 27         Max=0; 28         for(i=1;i<=n;i++) 29         {
    30             k=0; 31             for(j=1;j<=m;j++) 32             {
    33                 if(map[i][j]=='1') 34                 {
    35                     dp[i][j]=dp[i-1][j]+1; 36                     s[++k]=dp[i][j]; 37                 } 38             } 39             qsort(s+1,k,sizeof(s[1]),cmp); 40             for(j=1;j<=k;j++) 41                 Max=max(Max,s[j]*(k-j+1)); 42         } 43         printf("%d\n",Max); 44     } 45     return 0; 46 }

hdu 3415 Max Sum of Max-K-sub-sequence

最大的序列和，不过这个序列的长度不能超过k.

在i点时的最大和为sum[i]-min(sum[j]); i-k<=j<=i

枚举会超时，这里就用到了单调队列。

单调队列即保持队列中的元素单调递增（或递减）的这样一个队列，可以从两头删除，只能从队尾插入。

单调队列的具体作用在于，由于保持队列中的元素满足单调性，对于上述问题中的每个j，可以用O(1)的时间找到对应的s[i]。

（保持队列中的元素单调增的话，队首元素便是所要的元素了）。

维护方法：对于每个j，我们插入s[j-1]（为什么不是s[j]? 队列里面维护的是区间开始的下标，j是区间结束的下标），插入时从队尾插入。

为了保证队列的单调性，我们从队尾开始删除元素，直到队尾元素比当前需要插入的元素优

（本题中是值比待插入元素小，位置比待插入元素靠前，不过后面这一个条件可以不考虑），就将当前元素插入到队尾。

之所以可以将之前的队列尾部元素全部删除，是因为它们已经不可能成为最优的元素了，因为当前要插入的元素位置比它们靠前，值比它们小。

我们要找的，是满足(i>=j-k+1)的i中最小的s[i]，位置越大越可能成为后面的j的最优s[i]。

View Code

1 # include
      
         2 # include
       
          3 # define N 100005  4 int a[2*N],sum[2*N],s[2*N];  5 int main()  6 {
     7     int i,ncase,n,k,from,to,top,end,Max,m;  8     scanf("%d",&ncase);  9     while(ncase--) 10     {
    11         scanf("%d%d",&n,&k); 12         sum[0]=0; 13         for(i=1;i<=n;i++) 14         {
    15             scanf("%d",&a[i]); 16             sum[i]=sum[i-1]+a[i]; 17         } 18         for(i=n+1;i<=n+k-1;i++) 19             sum[i]=sum[i-1]+a[i-n]; 20         top=1; 21         end=1; 22         m=n; 23         n=n+k-1; 24         s[1]=0; 25         Max=(k+1)*(-1000); 26         for(i=1;i<=n;i++) 27         {
    28             while(end-top>=0 && sum[s[end]]>sum[i-1]) 29                 end--; 30             while(end-top>=0 && i-s[top]>k) 31                 top++; 32             s[++end]=i-1; 33             if(sum[i]-sum[s[top]]>Max) 34             {
    35                 Max=sum[i]-sum[s[top]]; 36                 from=s[top]+1; 37                 to=i; 38             } 39         } 40         printf("%d %d %d\n",Max,from,(to-1)%m+1); 41     } 42     return 0; 43 }

hdu 2993 MAX Average Problem

看见此题就用dp开始乱搞，最后跑了700ms+wa了。。

这里要用到斜率优化，给大家推荐一篇不错的论文：

View Code

1 # include
      
         2 # include
       
          3 # define N 100005  4 double sum[N];  5 int top,s[N];  6 double K(int i,int j,int k)  7 {
     8     double tmp;  9     tmp=(k-i)*(sum[j]-sum[i])-(j-i)*(sum[k]-sum[i]); 10     return tmp; 11 } 12 double max(double a,double b) 13 {
    14     return a>b?a:b; 15 } 16 int readT() 17 {
    18     char c; 19     int ret; 20     while(c=getchar(),c<'0'||c>'9'); 21     ret = c - '0'; 22     while(c=getchar(),c>='0'&&c<='9') ret = ret * 10 + c-'0'; 23     return ret; 24 } 25 double asc(int i,int k) 26 {
    27     i=s[i]; 28     return (sum[k]-sum[i])/(k-i); 29 } 30 int main() 31 {
    32     int i,j,n,k,f; 33     double Max; 34     while(scanf("%d%d",&n,&k)!=EOF) 35     {
    36         sum[0]=0; 37         for(i=1;i<=n;i++) 38             sum[i]=sum[i-1]+readT(); 39         top=0; 40         f=0; 41         Max=0; 42         for(i=k;i<=n;i++) 43         {
    44             j=i-k; 45             while(top-f>=1 && K(s[top-1],s[top],j)>=0) top--; 46             s[++top]=j; 47             while(top-f>=1 && asc(f+1,i)>=asc(f,i)) 48                 f++; 49             Max=max(Max,asc(f,i)); 50         } 51         printf("%.2lf\n",Max); 52     } 53     return 0; 54 }

hdu 1950 Bridging signals

转化为求最长上升子序列。

数据比较大，用二分法。

View Code

1 # include
      
         2 # include
       
          3 # define N 40005  4 int top,s[N],a[N];  5 int find(int x)  6 {
     7     int left,mid,right,ans;  8     left=1;  9     right=top; 10     if(x>s[top]) return ++top; 11     while(right>=left) 12     {
    13         mid=(left+right)/2; 14         if(s[mid]==x) return mid; 15         if(s[mid]>x) {ans=mid;right=mid-1;} 16         else left=mid+1; 17     } 18     return ans; 19 } 20 int main() 21 {
    22     int i,n,ncase,ans; 23     scanf("%d",&ncase); 24     while(ncase--) 25     {
    26         scanf("%d",&n); 27         for(i=1;i<=n;i++) 28             scanf("%d",&a[i]); 29         s[1]=a[1]; 30         top=1; 31         for(i=2;i<=n;i++) 32         {
    33             ans=find(a[i]); 34             s[ans]=a[i]; 35         } 36         printf("%d\n",top); 37     } 38     return 0; 39 }