【01背包问题】【题目收集】1.dd爱科学2. 九小时九个人九扇门3.智乃买瓜4.爆炸的符卡洋洋洒洒5. 5倍经验日

125 阅读 0 评论 83 点赞

我是靠谱客的博主微笑小刺猬，这篇文章主要介绍【01背包问题】【题目收集】1.dd爱科学2. 九小时九个人九扇门3.智乃买瓜4.爆炸的符卡洋洋洒洒5. 5倍经验日，现在分享给大家，希望可以做个参考。

1.dd爱科学

https://ac.nowcoder.com/acm/contest/11211/C

一串字符串，要求必须不递减，可以对字母进行修改，修改代价为原字母和修改后字母的差距，求最小修改代价和

状态表示：

$f [i] [j]$ ：前i个字母，第i个字母修改为j的最小代价

状态转移：
$f [i] [j] = m i n (f [i] [j], f [i - 1] [k] + a b s (s [i - 1] -^{'} A^{'} - j))$
因为可以从任意比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
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5; 

int main()
{
	int n;
	cin>>n;
	vector<vector<int>>f(n+1,vector<int>(26,1e9));
	string s;
	cin>>s;
	
	f[0][0] = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<26;j++)
		{
//			f[i][j] = f[i-1][j] + abs(s[i-1]-'A'-j);
			for(int k=0;k<=j;k++)
				f[i][j] = min(f[i][j],f[i-1][k] + abs(s[i-1]-'A'-j));
		}
	}
	int res = 1e9;
	for(int i=0;i<26;i++)
		res = min(res,f[n][i]);
	cout<<res<<endl;
	return 0;
}

2. 九小时九个人九扇门

链接：
https://ac.nowcoder.com/acm/contest/23106/A

数字根：一个数字的数字跟为该数字各个位数之和，对于这个结果再对其各个位数求和，直到求出来的结果为一个数字，即小于10，最终得出的结果为初始数字的数字根。
有n个人，每个人都有一个数字，不同的人可以组合在一起。共标有1-9号数字的9扇门，只有数字跟和门上数字相等才能打开门，求开每种门的所有组合情况数。

数字根的几个性质

先对数字根分析：
对于两个数x和y,可以发现 x+y的数字根 $=$ ·x的数字根+y的数字根
也就是说，数字根的计算顺序并不影响最终得出的数字根的结果

那么就可动态规划：
状态表示：
$f [i] [j]$ :前i个人，数字根为j的组合情况
状态转移：
count()函数是计算数字根的函数
不选中第i个人时： $f [i] [j] = f [i - 1] [j]$ （注意要先转移所有的不选中的，再进行下面的操作）
选中第i个人时： $f [i] [c o u n t (j + a [i])] + = f [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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5,mod = 998244353;

ll a[N],f[N][10];
ll count(ll x)
{
	while(x>=10)
	{
		int cnt = 0;
		while(x)
		{
			cnt += x % 10;
			x /= 10;
		}
		x = cnt;
	}
	return x;
}

void solve()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		ll x;
		scanf("%lld",&x);
		a[i] = count(x);
	}
	//初始化
	for(int i=0;i<=n;i++) f[i][0] = 1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=9;j++) f[i][j] = f[i-1][j];
		for(int j=0;j<=9;j++) f[i][count(j+a[i])] =(f[i][count(j+a[i])] + f[i-1][j]) % mod;
	}
	for(int i=1;i<=9;i++) printf("%lld ",f[n][i]);
}
int main()
{
	int t;
	t = 1;
	while(t--) solve();
 	return  0;
 }

3.智乃买瓜

https://ac.nowcoder.com/acm/contest/23478/B

n个瓜，第i个瓜的重量为 $w_i$ ，对于每个西瓜，可以选择买一个，买半个，或者不买，求买瓜重量为k=1,2,3,...,M时，总方案数

状态表示：
$f [i] [j]$ :前i个瓜，买了j重量的方案数
状态转移：
$f[i][j]=f[i-1][j-w_{i}]+f[i-1][j-frac{w_i}{2}]+f[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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
typedef pair<int,int> pii;
typedef long long ll;
ll mod = 1e9+7;


int f[N][N];
int a[N];

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=0;i<=n;i++) f[i][0] = 1;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			f[i][j] = f[i-1][j];
			if(j>=a[i]) f[i][j] = (f[i][j] + f[i-1][j-a[i]]) % mod;
			if(j>=a[i]/2) f[i][j] =(f[i][j] + f[i-1][j-a[i]/2])%mod;
		}
	}
	
	for(int i=1;i<=m;i++) cout<<f[n][i]<<" ";
	
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int t;
//	cin>>t;
	t = 1;
	while(t--) solve();
	return 0;
 }

4.爆炸的符卡洋洋洒洒

链接：
https://ac.nowcoder.com/acm/problem/230607

在这里插入图片描述

转移时注意：
只能从j=0和f[i-1][j]值不为0（说明f[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
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 15002,mod = 1000000007;

ll f[1005][1005];
ll a[1005],b[1005];

void solve()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<k;j++)
			f[i][j] = f[i-1][j];

		for(int j=0;j<k;j++)
		{
		//因为j+a[i]是新生成的，不能和上一个循环写在一起
			if(f[i-1][j] || j==0)
				f[i][(j+a[i])%k] = max(f[i][(j+a[i])%k],f[i-1][j] + b[i]);
		}
	}
	if(f[n][0]) cout<<f[n][0]<<endl;
	else cout<<-1<<endl;
	
}

int main()
{
	int t;
//	scanf("%d",%t);
	t = 1;
//	cin>>t;
	while(t--) solve();
	return 0;
 }

复制代码

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

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int>a(n+1), b(n+1);
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	
	vector<vector<ll>>f(n+1,vector<ll>(k,-1e18));
	
	f[0][0] = 0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<k;j++)
	 	{
	 		f[i][j] = f[i-1][j];
	 		f[i][j] = max(f[i][j],f[i-1][(j-a[i]%k+k)%k]+b[i]);
		}
	
	if(f[n][0] <= 0) cout<<-1<<endl;
	else cout<<f[n][0]<<endl;
	return 0;
 }

5. 5倍经验日

https://www.luogu.com.cn/problem/P1802

n个好友，要第i个好友至少需要 $s_i$ 瓶药，胜利会获得 $w_i$ 经验，失败获得 $l_i$ 经验，求获得最大经验再乘5

我尝试了新的一种写法
状态表示：
$f [i] [j]$ ：前i个好友，药水数为j，获得最大经验值
状态转移：
$f [i] [j] = m a x (f [i - 1] [j] + l o s e [i], f [i - 1] [j - s [i]] + w i n [i])$

我声明了两个数组dp和ndp,利于节省空间
ndp[j]代表当前物品的状态,等价于f[i][j]
dp[j]代表前一个物品的状态，等价于f[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<bits/stdc++.h>
using namespace std;
using ll = long long ;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	vector<ll> dp(m + 1, 0), ndp(m + 1, 0);
	
	for(int i = 1; i <= n; i++ )
	{
		int lose, win, s;
		cin >> lose >> win >> s;
		for(int j = 0; j <= m; j++)
		{
			ndp[j] = dp[j] + lose;
			if(j >= s) ndp[j] = max(dp[j - s] + win, ndp[j]);
		}
		dp = ndp;
	}	
	cout << dp[m] * 5 << "n";
	return 0;
}