基础动态规划

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 8 分钟
  • 1、线性dp：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给定一个数列，求其中最长上升子序列的长度：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n;
int a[N],f[N];
int ans; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		a[i]=qread();
	}
	for(re int i=1;i<=n;i++)
	{
		for(re int j=0;j<i;j++)
		{
			if(a[i]>a[j])
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
		ans=max(ans,f[i]);
	}
	qwrite(ans);
	putchar('\n');
	return 0;
}
  • 2、多维dp：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=1010;
using namespace std;
int n;
int a[N][N],f[N][N]; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
int main()
{
	n=qread();
	for(re int i=1;i<=n;i++)
	{
		for(re int j=1;j<=i;j++)
		{
			a[i][j]=qread();
		}
	}
	for(re int i=n;i;i--)
	{
		for(re int j=i;j;j--)
		{
			f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);
		}
	}
	qwrite(f[1][1]);
	putchar('\n');
	return 0;
}

  • 3、背包dp：

    \(\qquad\!\!\)背包dp 是一类非常典型的 dp 题，通常表示为：有具有一定大小的背包和具有一定大小和价值的物品，最优决策使选取的物品的价值最大。因为对于背包、物品以及选取方式的不同的修饰限制，产生了不同种类的背包以及不同种类的背包优化。

    \(\qquad\!\!\)注意一点，根据题目要求，有的题目要求背包内所有空间必须全部用上，有的不要求。

    • ①、01背包：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1048 采药：

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    const int N=10010;
    using namespace std; 
    int n,m;
    int v[N],val[N],f[N];
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
    		{
    			y=-1;
    		}
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		qwrite(-x);
    	}
    	else
    	{
    		if(x>9)
    		{
    			qwrite(x/10);
    		}
    		putchar(x%10+'0');
    	}
    	return ;
    }
    int main()
    {
    	n=qread();
    	m=qread();
    	for(re int i=1;i<=m;i++)
    	{
    		v[i]=qread();//输入体积
    		val[i]=qread();//输入价值 
    	}
    	for(re int i=1;i<=m;i++)
    	{
    		for(re int j=n;j>=v[i];j--)//从后向前扫
    		{
    			f[j]=max(f[j],f[j-v[i]]+val[i]);//取减去体积并加上价值与不取此物品的价值的较大值 
    		}
    	}
    	qwrite(f[n]);//输出最大的空间装的最大的价值 
    	putchar('\n');
    	return 0;
    }

    • ②、完全背包：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1616 疯狂的采药：

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    #define int long long
    const int N=10010;
    const int M=10000010;
    using namespace std;
    int n,m;
    int v[N],val[N],f[M];
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
            {
                y=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
        if(x<0)
        {
            putchar('-');
            qwrite(-x);
        }
        else
        {
            if(x>9)
            {
                qwrite(x/10);
            }
            putchar(x%10+'0');
        }
        return ;
    }
    signed main()
    {
        n=qread();
        m=qread();
        for(re int i=1;i<=m;i++)
        {
            v[i]=qread();
            val[i]=qread(); 
        }
        for(re int i=1;i<=m;i++)
        {
            for(re int j=v[i];j<=n;j++)
            {
                f[j]=max(f[j],f[j-v[i]]+val[i]);
            }
        }
        qwrite(f[n]);
        putchar('\n');
        return 0;
    }

    • ③、01背包前 \(k\) 优解：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1858 多人背包

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    const int N=210;
    const int M=5050;
    const int K=60;
    using namespace std; 
    int k,n,m;
    int v[N],val[N],f[M][K];
    int ans;
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
    		{
    			y=-1;
    		}
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		qwrite(-x);
    	}
    	else
    	{
    		if(x>9)
    		{
    			qwrite(x/10);
    		}
    		putchar(x%10+'0');
    	}
    	return ;
    }
    int main()
    {
    	k=qread(); 
    	m=qread();
    	n=qread();
    	for(re int i=1;i<=n;i++)
    	{
    		v[i]=qread();
    		val[i]=qread();
    	}
    	memset(f,-0x3f,sizeof(f));
    	f[0][1]=0;
    	for(re int i=1;i<=n;i++)
    	{
    		for(re int j=m;j>=v[i];j--)
    		{
    			int l=1,r=1,cnt=0,temp[K];
    			while(cnt<=k)
    			{
    				if(f[j][l]>f[j-v[i]][r]+val[i])
    				{
    					temp[++cnt]=f[j][l++];
    				}
    				else
    				{
    					temp[++cnt]=f[j-v[i]][r++]+val[i];
    				}
    			}
    			for(re int i=1;i<=k;i++)
    			{
    				f[j][i]=temp[i];
    			}
    		}
    	}
    	for(re int i=1;i<=k;i++)
    	{
    		ans+=f[m][i];
    	}
    	qwrite(ans); 
    	putchar('\n');
    	return 0;
    }

    • ④、分组背包：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1757 通天之分组背包：

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    const int N=1010;
    using namespace std;
    int n,m;
    int cnt,maxx;
    int v[N],val[N];
    int bh[N][N],tot[N];
    int f[N];
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
    		{
    			y=-1;
    		}
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		qwrite(-x);
    	}
    	else
    	{
    		if(x>9)
    		{
    			qwrite(x/10);
    		}
    		putchar(x%10+'0');
    	}
    	return ;
    }
    int main()
    {
    	m=qread();
    	n=qread();
    	for(re int i=1;i<=n;i++)
    	{
    		v[i]=qread();
    		val[i]=qread();
    		cnt=qread();
    		maxx=max(maxx,cnt);
    		bh[cnt][++tot[cnt]]=i;
    	}
    	for(re int i=1;i<=maxx;i++)
    	{
    		for(re int j=m;~j;j--)
    		{
    			for(re int k=1;k<=tot[i];k++)
    			{
    				if(j>=v[bh[i][k]])
    				{
    					f[j]=max(f[j],f[j-v[bh[i][k]]]+val[bh[i][k]]);
    				}
    			}
    		}
    	}
    	qwrite(f[m]);
    	putchar('\n');
    	return 0;
    }

    • ⑤、多重背包：

      \(\qquad\!\!\)例题：

      \(\qquad\!\!\)P1776 宝物筛选：

      • (1)、二进制分组：把每组物品对于个数按二进制分组，以表示全部物品。相当于增加物品的数量转化为 01背包：

      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
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      #include<bits/stdc++.h>
      #define in inline
      #define re register
      const int N=100010;
      const int M=40010;
      using namespace std;
      int n,m,s;
      int v[N*20],w[N*20],f[M];
      in int qread()
      {
          int x=0,y=1;
          int ch=getchar();
          while(ch<'0'||ch>'9')
          {
              if(ch=='-')
              {
                  y=-1;
              }
              ch=getchar();
          }
          while(ch>='0'&&ch<='9')
          {
              x=(x<<1)+(x<<3)+(ch^48);
              ch=getchar();
          }
          return x*y;
      }
      in void qwrite(re int x)
      {
          if(x<0)
          {
              putchar('-');
              qwrite(-x);
          }
          else
          {
              if(x>9)
              {
                  qwrite(x/10);
              }
              putchar(x%10+'0');
          }
          return ;
      }
      int main()
      {
          m=qread();
          s=qread();
          while(m--)
          {
              int x=qread();
              int y=qread();
              int z=qread();
              int p=1;
              while(z>=p)
              {
                  v[++n]=y*p;
                  w[n]=x*p;
                  z-=p;
                  p<<=1;
              } 
              if(z)
              {
                  v[++n]=y*z;
                  w[n]=x*z;
              }
          }
          for(re int i=1;i<=n;i++)
          {
              for(re int j=s;j>=v[i];j--)
              {
                  f[j]=max(f[j],f[j-v[i]]+w[i]);
              }
          }
          qwrite(f[s]);
          putchar('\n');
          return 0;
      }

      • (2)、单调队列优化：按照对于每个物品的空间取模分组，每组内对于取的 个数-空间 单调队列优化，保证每个空间下只转移一次。

      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
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      #include<bits/stdc++.h>
      #define in inline
      #define re register
      const int N=100010;
      const int M=40010;
      using namespace std;
      int n,s;
      int f[M],ans;
      struct node
      {
          int pos,val;
      };
      node q[N];
      int h,t;
      in int qread()
      {
          int x=0,y=1;
          int ch=getchar();
          while(ch<'0'||ch>'9')
          {
              if(ch=='-')
              {
                  y=-1;
              }
              ch=getchar();
          }
          while(ch>='0'&&ch<='9')
          {
              x=(x<<1)+(x<<3)+(ch^48);
              ch=getchar();
          }
          return x*y;
      }
      in void qwrite(re int x)
      {
          if(x<0)
          {
              putchar('-');
              qwrite(-x);
          }
          else
          {
              if(x>9)
              {
                  qwrite(x/10);
              }
              putchar(x%10+'0');
          }
          return ;
      }
      int main()
      {
          n=qread();
          s=qread();
          for(re int i=1;i<=n;i++)
          {
              int w=qread();
              int v=qread();
              int num=qread();
              num=min(num,s/v);
              for(re int j=0;j<v;j++)
              {
                  for(re int i=0;i<=t;i++)
                  {
                      q[i]=(node){0,0};
                  }
                  h=t=0;
                  for(re int k=0;k<=(s-j)/v;k++)
                  {
                      int x=k;
                      int y=f[k*v+j]-k*w;
                      while(h<=t&&q[h].pos<k-num)
                      {
                          h++;
                      }
                      while(h<=t&&q[t].val<=y)
                      {
                          t--;
                      }
                      q[++t]=(node){x,y};
                      f[k*v+j]=q[h].val+k*w;
                  }
              }
          }
          for(re int i=1;i<=s;i++)
          {
              ans=max(ans,f[i]);
          }
          qwrite(ans);
          putchar('\n');
          return 0;
      }

    • ⑥、混合背包：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1833 樱花：

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    const int N=1010;
    using namespace std;
    int t1,t2,s,n;
    int f[N];
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
            {
                y=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
        if(x<0)
        {
            putchar('-');
            qwrite(-x);
        }
        else
        {
            if(x>9)
            {
                qwrite(x/10);
            }
            putchar(x%10+'0');
        }
        return ;
    }
    int main()
    {
        int hh=qread();
        int mm=qread();
        t1=hh*60+mm;
        hh=qread();
        mm=qread();
        t2=hh*60+mm;
        s=t2-t1;
        n=qread();
        for(re int i=1;i<=n;i++)
        {
            int t=qread();
            int c=qread();
            int p=qread();
            if(!p)
            {
                for(re int j=t;j<=s;j++)
                {
                    f[j]=max(f[j],f[j-t]+c);
                }
            }
            else
            {
                int q=1,o=1;
                int v[20],w[20];
                while(p>=q)
                {
                    v[++o]=t*q;
                    w[o]=c*q;
                    p-=q;
                    q<<=1;
                }
                if(p)
                {
                    v[++o]=t*p;
                    w[o]=c*p;
                }
                for(re int k=1;k<=o;k++)
                {
                    for(re int j=s;j>=v[k];j--)
                    {
                        f[j]=max(f[j],f[j-v[k]]+w[k]);
                    }
                }
            }
        }
        qwrite(f[s]);
        putchar('\n');
        return 0;
    }

    • ⑦、二维费用：

    \(\qquad\!\!\)例题：

    \(\qquad\!\!\)P1509 找啊找啊找GF：

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include<bits/stdc++.h>
    #define in inline
    #define re register
    const int N=110;
    using namespace std;
    int n,m,r; 
    int rmb[N],rp[N],tim[N];
    int f[N][N],ft[N][N];
    in int qread()
    {
        int x=0,y=1;
        int ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
            {
                y=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*y;
    }
    in void qwrite(re int x)
    {
        if(x<0)
        {
            putchar('-');
            qwrite(-x);
        }
        else
        {
            if(x>9)
            {
                qwrite(x/10);
            }
            putchar(x%10+'0');
        }
        return ;
    }
    int main()
    {
        n=qread();
        for(re int i=1;i<=n;i++)
        {
            rmb[i]=qread();
            rp[i]=qread();
            tim[i]=qread();
        }
        m=qread();
        r=qread();
        for(re int i=1;i<=n;i++)
        {
            for(re int j=m;j>=rmb[i];j--)
            {
                for(re int k=r;k>=rp[i];k--)
                {
                    if(f[j][k]<f[j-rmb[i]][k-rp[i]]+1)
                    {
                        f[j][k]=f[j-rmb[i]][k-rp[i]]+1;
                        ft[j][k]=ft[j-rmb[i]][k-rp[i]]+tim[i];
                    }
                    else if(f[j][k]==f[j-rmb[i]][k-rp[i]]+1)
                    {
                        ft[j][k]=min(ft[j][k],ft[j-rmb[i]][k-rp[i]]+tim[i]);
                    }
                }
            }
        }
        qwrite(ft[m][r]);
        putchar('\n');
        return 0;
    }