第五课 动规

A 最少末尾0

思路

首先末尾有 $0$，那么自然是要相乘的数中的因数包含 $2$ 和 $5$。

那么我们就可以预处理出输入矩阵中因数 $2$ 和 $5$ 的个数，然后在以此的基础上进行动态规划。

我们可以分别动态规划最少的 $2$ 和 $5$，然后取最小的就行了，因为一个 $2$ 对应一个 $5$ 才能凑成 $0$，那么最小值自然就是末尾 $0$ 的最小值了。

不过还有 $0$ 的特殊情况没有考虑。

如果一个矩阵有 $0$ ，那么乘积自然为 $0$ ，相当于一个末尾零。所以我们可以特判动态规划的结果，如果不走 $0$ 的路至少有一个末尾 $0$，那么就可以直接找到 $0$ 的位置，然后构造一条路径，如下图：

那么如果不走有 $0$ 的路径，我们就通过 $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
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
#include <bits/stdc++.h>
using namespace std;

long long a[1010][1010];
long long dp[1010][1010][2];
string ans;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]);
	}
	int pos=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==0) //0:2 1:5
			{
				pos=i;
				dp[i][j][0]=1e9;
				dp[i][j][1]=1e9;
				continue;
			}
			long long k=a[i][j];
			while(k!=0 && k%2==0) dp[i][j][0]++,k/=2;
			k=a[i][j];
			while(k!=0 && k%5==0) dp[i][j][1]++,k/=5; 
		}
	}
	for(int i=2;i<=n;i++)
	{
		dp[1][i][0]+=dp[1][i-1][0];dp[1][i][1]+=dp[1][i-1][1];
		dp[i][1][1]+=dp[i-1][1][1];dp[i][1][0]+=dp[i-1][1][0];
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			dp[i][j][0]+=min(dp[i-1][j][0],dp[i][j-1][0]);
			dp[i][j][1]+=min(dp[i-1][j][1],dp[i][j-1][1]);//0:2 1:5
		}
	}
	int k=0;
	if(dp[n][n][0]>=dp[n][n][1]) k=1;
	if(pos!=-1 && dp[n][n][k]>0)
	{
		//cout<<"nihao";
		puts("1");
		for(int i=1;i<pos;i++) printf("D");
		for(int i=1;i<n;i++) printf("R");
		for(int i=pos;i<n;i++) printf("D");
		return 0;
	}/*
	3
	1 2 3
	0 0 0
	4 5 6
	*/
	int i=n,j=n;
	while(true)
	{
		if(dp[i-1][j][k]<dp[i][j-1][k])//比较状态，回溯。
		{
			ans+="D";
			i--;
		}
		else ans+="R",j--;
		if(i==1)
		{
			for(int kk=1;kk<j;kk++) ans+="R";
			break;
		}
		else if(j==1)
		{
			for(int kk=1;kk<i;kk++) ans+="D";
			break;
		}
	}
	printf("%d\n",dp[n][n][k]);
	int t=ans.size()-1;
	for(int i=t;i>=0;i--) printf("%c",ans[i]);
}

B 最小的最长上升子序列

思路

这道题我们设 $dp_i$ 为以 $i$ 开头的最长上升子序列的长度。

而由于输出要求字典序最小，我们还需要维护一个 $st$ 数组，表示以 $i$ 开头的最长上升子序列的结尾最大值。

考虑如何维护 $st$ 数组。

  1. 如果当前数能直接放在 $st$ 数组里，就直接放。
  2. 否则将 $st$ 数组里的最小于等于当前数的那个数替换成当前数。

代码

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
#include<bits/stdc++.h>
using namespace std;

int n;
int a[100010];

int dp[100010];
vector<int >st;

void Input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
}

int find(int x) {
    int l = 0, r = st.size() - 1, best = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (st[mid] <= x) {
            r = mid - 1;
            best = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return best;
}

void Work() {
    st.push_back(a[n]);
    dp[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        if (a[i] < st[st.size() - 1]) {
            st.push_back(a[i]);
            dp[i] = st.size();
        }
        else {
            int pos = find(a[i]);
            dp[i] = pos + 1;
            st[pos] = a[i];
        }
    }
    vector<int >ans;
    int len = st.size();
    int f = 1, pre = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= i; j--) {
            if (dp[j] == len && a[j] > pre) {
                ans.push_back(a[j]);
                f = 0;
                i = j - 1;
                pre = a[j];
                len--;
                break;
            }
        }
    }
    if (f) {
        printf("orz");
        return;
    }
    for (int now = 0; now < ans.size(); now++) {
        printf("%d ", ans[now]);
    }
}

int main() {
    Input();
    Work();
    return 0;
}

C 拾牌游戏

思路

设 $dp_{i,j,k,l}$ 表示当前剩下的范围为第一堆牌的 $i$ 位置（左端点），第一堆牌的 $j$ 位置（右端点），第二堆牌的 $k$ 位置（左），第二堆牌的 $l$ 位置（右）。

然后记忆化搜索枚举所有状态

代码

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100010],b[100010];
int sum=0;
int dp[22][22][22][22];

int dfs(int l,int r,int ll,int rr,int sum)
{
	int ans=0;
	if(dp[l][r][ll][rr]!=-1) return dp[l][r][ll][rr];
	
	if(l<=r)
	{
		ans=max(ans,sum-dfs(l+1,r,ll,rr,sum-a[l]));
		ans=max(ans,sum-dfs(l,r-1,ll,rr,sum-a[r]));
	}
	if(ll<=rr)
	{
		ans=max(ans,sum-dfs(l,r,ll+1,rr,sum-b[ll]));
		ans=max(ans,sum-dfs(l,r,ll,rr-1,sum-b[rr]));
	}
	return dp[l][r][ll][rr]=ans;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=a[i];
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]),sum+=b[i];
	memset(dp,-1,sizeof dp);
	cout<<dfs(1,n,1,n,sum);
}

D 凑硬币

思路

这道题其实就是多重背包模板，分享一下我以前写得笔记。

1. 学习笔记

1.1 算法介绍

多重背包是告诉你有多少个物体重量以及价值，并且每种物品还外加了最多能取多少个。问你最大能凑出的价值。

1.2 算法流程

$$多重背包暴力做法$$

这个看过 完全背包 的同学应该不难想到，直接三重循环枚举空间和个数就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N];
int v[N],w[N],c[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//枚举空间
        {
            for(int k=0;k<=c[i] && k*v[i]<=j;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+w[i]*k);//枚举当前要选几遍当前物品
        }
    }
    printf("%d",dp[n][m]);
}

$$多重背包二进制优化$$

大家记不记得小学奥数中有一道题？
小明有 113 克的砝码 $13$ 个,请问最少要选其中多少个砝码才能称出 113 克中的所有重量？

这道小学奥数题不仅可以一个一个试，还可以用二进制。
我们只需要选 $1$，$2$，$4$，$8$…这样一个一个选过去就好了
为什么？
首先，$1$ 可以凑出 $1$
$1，2$ 可以凑数 13
那么 $1，2，4$ 就可以凑出 17
因为为 13 可以凑出来了，$4$ 有单独了，所以可以。而 57 就相当于是凑出 $4$ 加 $1$ 或 $2$ 或 $1+2$。
接下来看$1，2，4，8$。18 可以凑出来了 凑出 915 分两种情况

凑出 911 就相当于凑出 $8$ 加上 $1$ 和 $2$ 的所有相加组合
凑出1215相当于凑出 $8$ 加 $4$ 加 $1$ 和 $2$ 的所有相加组合

那么以此类推，每想凑出从当前数到下一项之间的所有数。就相当于当前项加上所有之前项的所有相加组合。
会不会感觉有点晕？看图：
屏幕截图 2023-06-08 230235.png

我们只需要要将判断当前物品可选的次数拆解成$ 1* w[i] ,2 * w [i] ,4 * w[i]… $这样打包。再做一遍$01$背包就能得出答案了。因为根据上面的结论，二进制可以凑出 所有情况下的数，那么也自然可以凑出选了每个遍数的物体。

那么只要按照上述内容将一个物体按照能选的遍数二进制差分当成多个物体，然后做一遍$01$背包问题就迎刃而解了。（点个关注+赞吧我写到这起码花了一个小时）

2. 模板题题解

暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N];
int v[N],w[N],c[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)//枚举空间
        {
            for(int k=0;k<=c[i] && k*v[i]<=j;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+w[i]*k);//枚举当前要选几遍当前物品
        }
    }
    printf("%d",dp[n][m]);
}

二进制优化

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
#include <bits/stdc++.h>
using namespace std;

const int N = 20010;
int dp[N];
int w[N],v[N];
int cnt=0;
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
    {
        int a,s,c;
        scanf("%d%d%d",&a,&s,&c);
        int k=1;
        while(k<=c)
        {
            cnt++;
            v[cnt]=a*k;//二进制差分，将v*k当成完整的一个物品使用
            w[cnt]=s*k;
            c-=k;
            k*=2;
        }
        if(c>0)//如果c减到剩下还有余话还得再打包，因为这说明二进制差分后还有余，不加上话c这个数凑不出来
        {
            cnt++;
            v[cnt]=a*c;
            w[cnt]=s*c;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
    printf("%d",dp[m]);
}

代码

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
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100010],b[100010];
vector<int> v;
int dp[1000010];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		int t=1;
		while(b[i]>=t)
		{
			b[i]-=t;
			v.push_back(t*a[i]);
			t*=2;
		}
		if(b[i]>0) v.push_back(b[i]*a[i]);
	}
	int t=v.size();
	dp[0]=1;
	for(int i=0;i<t;i++)
	{
		for(int j=m;j>=0;j--)
		{
			if(j>=v[i] && dp[j-v[i]]) dp[j]=1;
		}
	}
	int sum=0;
	for(int i=1;i<=m;i++) sum+=dp[i];
	printf("%d",sum);
}

E 补充括号

思路

这道题我们使用区间 $dp$，设状态 $dp_{i,j}$ 表示 $i,j$ 区间内的括号需要几次才能完美。

首先如果 $i,j$ 匹配，那么就转化成 $i+1,j-1$ 的问题了。

否则，我们可以枚举一个位置 $k$ ,把 $i,j$ 区间断成 $i,k$ 和 $k+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
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
#include<bits/stdc++.h>
using namespace std; 
int d[101][101];
int path[101][101];
string s;
bool match(char a, char b) {return (a == '(' && b == ')')||(a == '[' && b == ']');}

void print(int l,int r)
{
	if(l>r) return;
	if(l==r)
	{
		if(s[l]=='(' || s[l]==')') printf("()");
		else printf("[]");
		return;
	}
	if(path[l][r]==-1)
	{
		cout<<s[l];
		print(l+1,r-1);
		cout<<s[r];
	}
	else
	{
		print(l,path[l][r]);
		print(path[l][r]+1,r);
	}
}
int main() 
{
	
	getline(cin, s);
	int len = s.size();
	memset(d,0,sizeof(d));
	for(int i=0; i<len; i++)
	{
		d[i][i]=1;
	}
	for(int i=len-2;i>=0;i--)
	{
		for( int j=i+1;j<len;j++)
		{
			d[i][j]=0x3f3f3f3f;
			if(match(s[i],s[j]))
			{
				d[i][j]=d[i+1][j-1];
				path[i][j]=-1;
			}
			for(int k=i;k<j;k++)
			{
				if(d[i][k]+d[k+1][j]<d[i][j]) d[i][j]=d[i][k]+d[k+1][j],path[i][j]=k;
			}
		}
	}
	print(0,len-1);
	return 0;
}

学习课程

思路

这道题其实就是 $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
#include <bits/stdc++.h>
using namespace std;

vector<int> v,w;

int a[101][101];
int n,m;
int dp[1000];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=m;k>=0;k--) if(j>=k) dp[j]=max(dp[j],dp[j-k]+a[i][k]);
		}
	}
	printf("%d",dp[m]);
}

选取信号

思路

首先，为了不相交，每个信号都得选取大于等于他的信号。

也就是说，选的信号对应的信号必须是严格上升的。

那么这道题就直接转换成了求最长公共子序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int T,n,a[100010];
bool cmp(int x,int y){
	return x<y;
}
int main(){
		scanf("%d",&n);
		int ans=0;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			int *x=lower_bound(a,a+ans,a[i],cmp);
			if(x==a+ans) ans++;
			*x=a[i];
		}
		printf("%d\n",ans);
	
	return 0;
}

回文构造

思路

用正着的字符串和倒着的做最长公共子序列，和 $n$ 的差值就是答案。

最长公共子序列

设 $dp_{i,j}$ 为第一个字符串前 $i$ 个字符和第二个字符串前 $j$ 个字符的最长公共子序列。

涉及两种转移：

  1. 当 $s_i==s1_j$ 那么 $dp_{i,j}=dp_{i-1,j-1}+1$，因为两个相等，那么就算之前的匹配数加上这一个。
  2. 否则答案为 $max(dp_{i-1,j},dp_{i,j-1})$。也就是相当于没有匹配。

代码

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N];

char s[N],s1[N];

int main()
{
	int __;__=1;
	while(__--)
	{
		scanf("%s",s+1);
		int t=strlen(s+1);
		reverse(s+1,s+t+1);
		for(int i=1;i<=t;i++) s1[i]=s[i];
		reverse(s+1,s+t+1);
		for(int i=1;i<=t;i++)
		{
			for(int j=1;j<=t;j++)
			{
				if(s[i]==s1[j]) dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
		printf("%d\n",t-dp[t][t]);
		memset(dp,0,sizeof(dp));
	}
}

I 最大子矩阵和

思路

两个做法。

做法1

做二维前缀和，然后暴力枚举矩阵，时间复杂度 $O(n^4)$ 。

做法2

给每一个列做前缀和，然后每次枚举两行，表示子矩阵的上界和下界，利用刚刚做的列前缀和，做最大子段和，这样就直接相当于找出了以枚举的两行为上下界的最大子矩阵。时间复杂度 $O(n^3)$。

代码

做法1

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int a[N][N];
int s[N][N];

int main()
{
	int n,m;
	int mx=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
	}
	int anm=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=i;x<=n;x++) for(int y=j;y<=n;y++)
    {
        anm=max(anm,s[x][y]-s[i-1][y]-s[x][j-1]+s[i-1][j-1]);
	}
	printf("%d",anm);
}

做法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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 210;

int a[N][N];
int dp[N];
int s[N][N];

signed main()
{
	int n;
	while(scanf("%lld",&n)!=-1)
	{
		for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&a[i][j]);
			s[i][j]=s[i-1][j]+a[i][j];
		}
	}
	int mx=-1231333323;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			dp[1]=s[j][1]-s[i-1][1];
			mx=max(mx,dp[1]);
			for(int k=2;k<=n;k++) dp[k]=max(dp[k-1]+s[j][k]-s[i-1][k],s[j][k]-s[i-1][k]),mx=max(dp[k],mx);
		}
        memset(dp,0,sizeof dp);
	}
	printf("%lld\n",mx);
	}
	
}