C++ 背包DP

2022.01.31cf Educational Codeforces Round 122(Div2)

2022.01.31cf Educational Codeforces Round 122(Div 2)补题

Posted by zhangmh on 2022-02-02
Estimated Reading Time 6 Minutes
Words 1.4k In Total
Viewed Times

第一次打Div 2！看春晚哪有cf香哇

A. Div. 7

img

给出一个数，要求改变最少的位数上的数字使得该数字成为7的倍数，输出这个7的倍数。

思路：分情况讨论，若该数是7的倍数直接输出，若不是，在每10个数中必有7的倍数，那就对其对7的模处理。例如377 mod 7=6，那我们可以选择输出377+(7-1)=378，也可以输出377-6=371，为统一输出原则，尽可能输出较小的数，这样改变1位即可完成修改，但是若是减去余数需改变两位，那我们选择加上7-余数。

AC代码：

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;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	if(n%7==0) cout<<n<<'\n';
    	else
    	{
    		int x=n%7;
    		if(n-x>=n/10*10) cout<<n-x<<'\n';
    		else 
    		cout<<n+(7-x)<<'\n';
		}
	}
	return 0;
}

os：一开始这个题卡了十分钟欸，一直在想7的倍数有什么性质。。。

B. Minority

img

给出一个01字串，可以任意选择一连续字串，把0和1中个数较少的全部去掉，求最多可以去掉多少位。

思路：遍历字符串，记录0和1的个数，若两者出现次数不同，此时我们选择整个字符串，那输出的就是出现次数少的那个；若出现次数相同，我们选择长度为字符串长度-1，那结果就是输出次数-1。

AC代码：

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

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
string s;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>s;
    	int a=0,b=0;
    	int len=s.length();
    	for(int i=0;i<len;i++)
    	{
    		if(s[i]=='0') a++;
    		if(s[i]=='1') b++;
		}
		if(a==b) cout<<a-1<<'\n';
		else if(a>b) cout<<b<<'\n';
		else if(b>a) cout<<a<<'\n';
	}
	return 0;
}

os：一开始不敢写，一看这个数据范围，1e4*2e5真的不会TLE么，没想到还真没T，不科学啊

C. Kill the Monster

img

M和怪兽打架，给出两方的生命值和攻击力，又给出k次增加M的生命值或攻击力的机会，每次使用机会可以增加w的攻击力或a的生命值，问M可以击败怪兽吗。

思路：暴力，判断a次用于增加生命值和b次用于增加攻击力（a+b=k）时是否是怪兽的生命值先小于等于0。

AC代码：

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

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll t,k,w;
ll hc,dc,hm,dm,a;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	bool flag=false;
    	cin>>hc>>dc;
    	cin>>hm>>dm;
    	cin>>k>>w>>a;
    	for(ll i=0;i<=k;i++)
    	{
    		if((hm+dc+i*w-1)/(dc+i*w)<=(hc+(k-i)*a+dm-1)/dm) 
			{
				flag=true;
				break;
			}
		}
		cout<<(flag?"YES":"NO")<<'\n';
	}
	return 0;
}

os：额好暴力

D. Make Them Equal

img

给出k次操作的机会，每次可以在每个a[i]上增加如题所说的一个数，若a[i]==b[i]，那增加c[i]的硬币，问最多可以获得多少硬币。

**思路：**预处理每个a[i]变为b[i]所需的操作次数，问题变为一个01背包问题，即在k次操作下可以获得的最大硬币数。

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5;
int t,n,k,b[N],c[N],f[N][N*16],g[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    for(int i=2;i<=2000;i++) g[i]=1e6+10;
    for(int i=1;i<=1000;i++)
    {
    	for(int j=1;j<=i;j++)//模拟x，x的极限值就是i，再大无意义了
    	{
    		g[i+i/j]=min(g[i+i/j],g[i]+1);//类似递推，模拟a b数组转换关系
		}
	}
	cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	memset(b,0,sizeof(b));
    	memset(c,0,sizeof(c));
    	memset(f,0,sizeof(f));
    	k=min(12*n,k);
    	for(int i=1;i<=n;i++) cin>>b[i];
    	for(int i=1;i<=n;i++) cin>>c[i];
    	for(int i=1;i<=n;i++)//01背包
    	{
    		for(int j=0;j<=k;j++)
    		{
    			f[i][j]=f[i-1][j];
    			if(j>=g[b[i]])
    			f[i][j]=max(f[i][j],f[i-1][j-g[b[i]]]+c[i]);
			}                             //注意j减去的值
		}
		cout<<f[n][k]<<'\n';
	}
	return 0;
}

os：读题读了好久，又参考了网上的视频讲解，太菜了www

若有错误请指教orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
C++ 背包DP
FRIENDS
ESC