矩阵dp

矩阵dp

　　这里是矩阵dp，不是矩阵乘法优化dp。

　　矩阵上的dp好像也没什么特殊的？大概有一个套路就是从上向下，从左向右进行dp吧。

 　　

　　首先第一道题好像不是矩阵dp...

　　1005 矩阵取数游戏：https://www.luogu.org/problemnew/show/P1005

　　题意概述：在一个矩阵里面取数，每次从每行的左或右取一个数，并乘以$2^i$，$i$是取数的次数。直到取完为止，求最大得分。

　　看起来是道非常复杂的矩阵dp题，理性分析一下可以发现每一行之间并没有什么关系，所以分行做完以后再加起来就可以啦。那么在每一行内怎么做呢？像区间dp一样，用$dp[i][j]$表示取到剩下区间$[i][j]$时的最大得分。

　　然后再加上高精...

　　 
  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # define R register int
  5 
  6 using namespace std;
  7 
  8 int n,m,j;
  9 int len,a[81][81];
 10 int dp[81][81][1000];
 11 int P[81][100],ansc[81][1000],ans[1000];
 12 int t[1000];
 13 
 14 void add (int *a,int *b)
 15 {
 16     len=max(a[0],b[0])+2;
 17     for (R i=1;i<=len;++i)
 18     {
 19         a[i]+=b[i];
 20         a[i+1]+=a[i]/10;
 21         a[i]%=10;    
 22     }
 23     while (a[len]==0&&len) len--;
 24     a[0]=len;
 25 }
 26 
 27 void M (int *a,int *b)
 28 {
 29     if(a[0]>b[0]) return ;
 30     if(b[0]>a[0])
 31     {
 32         len=b[0];
 33         for (R i=0;i<=len;++i)
 34             a[i]=b[i];
 35         return ;
 36     }
 37     len=a[0];
 38     for (R i=len;i>=1;--i)
 39     {
 40         if(a[i]>b[i]) return ;
 41         if(a[i]==b[i]) continue;
 42         if(a[i]<b[i])
 43         {
 44             for (R j=0;j<=len;++j)
 45                 a[j]=b[j];
 46             return ;
 47         }
 48     }
 49 }
 50 
 51 void mul(int *a,int *b,int c)
 52 {
 53     len=b[0];
 54     for (R i=1;i<=len;++i)
 55         a[i]=b[i]*c;
 56     len+=3;
 57     for (R i=1;i<=len;++i)
 58         a[i+1]+=a[i]/10,a[i]%=10;
 59     while (a[len]==0&&len) len--;
 60     a[0]=len;
 61 }
 62 
 63 int main()
 64 {
 65     scanf("%d%d",&n,&m);
 66     P[0][0]=P[0][1]=1;
 67     for (R i=1;i<=80;++i)
 68     {
 69         P[i][0]=P[i-1][0]*2;
 70         len=P[i][0];
 71         for (R j=1;j<=len;++j)
 72             P[i][j]=P[i-1][j]*2;
 73         for (R j=1;j<=len;++j)    
 74             P[i][j+1]+=P[i][j]/10,P[i][j]%=10;
 75         while (P[i][len]==0&&len) len--;
 76         P[i][0]=len;
 77     }
 78     for (R i=1;i<=n;++i)
 79         for (R j=1;j<=m;++j)
 80             scanf("%d",&a[i][j]);
 81     for (R c=1;c<=n;++c)
 82     {
 83         memset(dp,0,sizeof(dp));
 84         memset(ansc,0,sizeof(ansc));
 85         for (R k=m;k>=1;k--)
 86             for (R i=1;i+k-1<=m;i++)
 87             {
 88                 j=i+k-1;
 89                 memset(t,0,sizeof(t));
 90                 mul(t,P[m-k+1],a[c][i]);
 91                 add(t,dp[i][j]);
 92                 M(dp[i+1][j],t);
 93                 memset(t,0,sizeof(t));
 94                 mul(t,P[m-k+1],a[c][j]);
 95                 add(t,dp[i][j]);
 96                 M(dp[i][j-1],t);
 97             }
 98         for (R i=1;i<=m;++i)
 99         {
100             mul(ansc[i],P[m],a[c][i]);
101             add(ansc[i],dp[i][i]);
102         }
103         for (R i=1;i<=m;++i)
104             M(ansc[1],ansc[i]);
105         add(ans,ansc[1]);
106     }
107     len=ans[0];
108     for (R i=len;i>=1;--i)
109         printf("%d",ans[i]);
110     if(len==0) printf("0");
111     return 0;
112 }
矩阵取数游戏

 

 

　　我发现我对矩阵这两个字大概是有什么误解吧，有的题不知道怎么归类，因为开了二维数组就进到矩阵dp这一栏里了？

　　垃圾陷阱：https://www.luogu.org/problemnew/show/P1156

　　题意概述：奶牛掉进了垃圾井，当有垃圾扔下来时，他可以吃掉，也可以堆放起来，问最短的出去时间，如果出不去，求最长的存活时间。

　　这道题有一个坑点，奶牛的生命值为0时还可以吃东西，堆垃圾，甚至跑出去...

　　用dp[i][j]表示用前i个物品，堆放高度为j时的最大生命值（能活到什么时候）。如果将一个垃圾堆起来，那它并不能续命，所以$dp[i][j]=max(dp[i-1][ j-h[i] ],dp[i][j])$；如果把垃圾吃了，那可以续一点命，但是不能增加高度，所以$dp[i][j]=max(dp[i][j],dp[i-1][j]+f[a])$.再处理一下边界就可以啦。

　　 
# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cstring>

using namespace std;

struct rubbi
{
    int t,f,h;
}a[102];

bool cmp(rubbi a,rubbi b)
{
    return a.t<b.t;
}

int d,g,ans=1e7;
int dp[102][200];

int main()
{
    int S=10;
    scanf("%d%d",&d,&g);
    for (int i=1;i<=g;i++)
      scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
    sort(a+1,a+1+g,cmp);
    memset(dp,-1,sizeof(dp));
    dp[0][0]=10;
    for (int i=1;i<=g;i++)
          for (int j=0;j<=d+40;j++)
          {
            if(dp[i-1][j-a[i].h]!=-1&&j>=a[i].h&&dp[i-1][j-a[i].h]>=a[i].t) 
                dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].h]);
            if(dp[i-1][j]!=-1&&dp[i-1][j]>=a[i].t) dp[i][j]=max(dp[i][j],dp[i-1][j]+max(a[i].f,0));
            if(dp[i][j]!=-1&&j>=d)
            {
                ans=min(ans,a[i].t);
            }
            if(dp[i][j]!=-1)
                S=max(S,dp[i][j]);
        }
    if(ans!=1e7) 
        printf("%d",ans);
    else
        printf("%d",S);
    return 0;
}
垃圾陷阱

 

　　

　　奶牛浴场：https://www.luogu.org/problemnew/show/P1578

　　题意概述：在一个有障碍的矩形中选出一个最大的子矩形，使得内部没有障碍点 (边界上可以有) 。

　　以前就做过这道题目，结果今天一看被Hack了，才发现之前学的那个方法不大对...这道题有两种做法，但是因为这题的障碍较少，所以第一种方法比较优也比较快。 

　　https://wenku.baidu.com/view/728cd5126edb6f1aff001fbb.html (扔完链接就跑路)

　　具体实现就不写了，毕竟论文讲的非常详细非常好，记录一下要注意的地方吧。

　  ·在矩形的四个顶点分别建立虚点。

　  ·有的矩形是左边有一个障碍点，有的是右边有一个障碍点，所以正着做一遍，反着做一遍。

　  ·有的矩形左右都没有障碍点，所以按照另一维坐标排序，将左右边界定为矩形的两边再统计一次答案。

　　·如果某一个障碍点和这次扫描的起点纵坐标相同就直接break。感觉好像会把一些合法情况排除掉呢，但是并不会。因为这两个点现在到了一条直线上，如果有合法答案必然会作为上边界或下边界，一个矩形有四个顶点，所以这样的情况必然还会在其他时间被枚举到。

　　  
 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 # define R register int
 5 
 6 using namespace std;
 7 
 8 int l,w,n,h,t,le,ans=0;
 9 struct nod
10 {
11     int x,y;
12 }P[5009];
13 
14 bool cmp1(nod a,nod b)
15 {
16     if(a.x==b.x) return a.y<b.y;
17     return a.x<b.x;
18 }
19 
20 bool cmp2(nod a,nod b)
21 {
22     return a.y<b.y;
23 }
24 
25 int main()
26 {
27     scanf("%d%d",&l,&w);
28     scanf("%d",&n);
29     for (R i=1;i<=n;++i)
30         scanf("%d%d",&P[i].x,&P[i].y);
31     P[n+1].x=0; P[n+1].y=0;
32     P[n+2].x=l; P[n+2].y=0;
33     P[n+3].x=0; P[n+3].y=w;
34     P[n+4].x=l; P[n+4].y=w;
35     sort(P+1,P+5+n,cmp1);
36     for (R i=1;i<=n+4;++i)
37     {
38         h=0,t=w;
39         le=P[i].x;
40         for (R j=i+1;j<=n+4;++j)
41         {
42             if(P[j].x==le) continue;
43             ans=max(ans,(t-h)*(P[j].x-le));
44             if(P[j].y==P[i].y) break;
45             if(P[j].y>P[i].y) t=min(t,P[j].y);
46             if(P[j].y<P[i].y) h=max(h,P[j].y);
47         }
48     }
49     for (R i=n+4;i>=1;--i)
50     {
51         h=0,t=w;
52         le=P[i].x;
53         for (R j=i-1;j>=1;j--)
54         {
55             if(P[j].x==le) continue;
56             ans=max(ans,(t-h)*(le-P[j].x));
57             if(P[j].y==P[i].y) break;
58             if(P[j].y>P[i].y) t=min(t,P[j].y);
59             if(P[j].y<P[i].y) h=max(h,P[j].y);
60         }
61     }
62     sort(P+1,P+5+n,cmp2);
63     for (R i=1;i<=n+3;++i)
64         ans=max(ans,l*(P[i+1].y-P[i].y));
65     printf("%d",ans);
66     return 0;
67 }
奶牛浴场

 

　　[HAOI2007]理想的正方形：https://www.luogu.org/problemnew/show/P2216

　　题意概述：在一个a*b的矩形中选出一个n*n的正方形，使得正方形内的最大值减去最小值最小，求这个最小值。$1<=a,b<=2000$

　　二维线段树！显然是可以的，但是没有必要。观察数据范围可以发现$O(N^3)$的暴力就可以跑过去，这就给了我们很大的启发，可以只统计区间的最大最小值，行与行之间暴力统计，既然是要求区间的最大最小值就可以用单调队列啦。还有一个很不错的做法可以进一步提高程序速度，拒绝暴力统计，在单调队列的基础上再开行的单调队列，就$N^2$了，但是感觉挺麻烦的就没写。

　　 
 1 // luogu-judger-enable-o2
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <iostream>
 5 # define R register int
 6 # define inf 1000000009
 7 
 8 using namespace std;
 9 
10 const int maxa=2005;
11 struct nod
12 {
13     int key,val;
14 };
15 nod q1[maxa],q2[maxa];
16 int a,b,n,h1,h2,t1,t2,big,sma;
17 int g[maxa][maxa];
18 int minn[maxa][maxa],maxx[maxa][maxa];
19 int ans=inf;
20 
21 void ins1 (int i,int j)
22 {
23     int x=g[i+n-1][j+n-1];
24     while (q1[h1].key<j&&h1<=t1) h1++;
25     while (q1[t1].val<=x&&h1<=t1) t1--;
26     q1[++t1].key=j+n-1;
27     q1[t1].val=x;
28 }
29 
30 void ins2 (int i,int j)
31 {
32     int x=g[i+n-1][j+n-1];
33     while (q2[h2].key<j&&h2<=t2) h2++;
34     while (q2[t2].val>=x&&h2<=t2) t2--;
35     q2[++t2].key=j+n-1;
36     q2[t2].val=x;
37 }
38 
39 int main()
40 {    
41     scanf("%d%d%d",&a,&b,&n);
42     for (R i=1;i<=a;++i)
43         for (R j=1;j<=b;++j)
44             scanf("%d",&g[i][j]);
45     for (R i=1;i<=a;++i)
46         for (R j=1;j<=b;++j)
47             minn[i][j]=inf;
48     for (R i=2-n;i<=a-n+1;++i)
49     {
50         memset(q1,0,sizeof(q1));
51         h1=h2=1;
52         memset(q2,0,sizeof(q2));
53         t1=t2=0;
54         for (R j=2-n;j<=b-n+1;++j)
55         {
56             ins1(i,j);
57             ins2(i,j);
58             if(j<1) continue;
59             maxx[i+n-1][j]=q1[h1].val;
60             minn[i+n-1][j]=q2[h2].val;
61             if(i<1) continue;
62             big=0,sma=inf;
63             for (int k=1;k<=n;++k)
64                 big=max(big,maxx[i+k-1][j]),sma=min(sma,minn[i+k-1][j]);
65             ans=min(ans,big-sma);
66         }
67     }
68     printf("%d",ans);
69     return 0;
70 }
[HAOI2007]理想的正方形

 --shzr

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/shzr/p/9275261.html