【贪心】ABC257 E - Addition and Multiplication 2

绝地灬酷狼 2024-03-23 14:40 70阅读 0赞

**暴力DP爆long long且T了**

**显然是要按位贪心**

[E - Addition and Multiplication 2 (atcoder.jp)][E - Addition and Multiplication 2 _atcoder.jp]

题意：

![eb69d8165d91431cb36e6fe32db03b89.png][]

思路：

一开始想的是暴力DP， 结果一发过样例之后爆long long且T了

DP Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    int w;
    int c[10];
    int dp[22][1000010][10];
    signed main(){
    	cin>>w;
    	for(int i=1;i<=9;i++) cin>>c[i];
    	int ans=-1;
    	for(int i=1;i<=9;i++) dp[1][c[i]][i]=i;
    	for(int i=2;i<=20;i++){
    		for(int j=0;j<=w;j++){
    			for(int k=1;k<=9;k++){
    				for(int z=1;z<=9;z++){
    					if(j>=c[k]){
    						dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-c[k]][z]*10+k);
    						ans=max(ans,dp[i][j][k]);
    					}
    				}
    			}
    		}
    	}
    	cout<<ans<<'\n';
    }

因此考虑按位贪心

对于每一位，都去从9到1枚举，如果合法该位就是该值

那么怎么样才算合法

当钱足够后面数字填满就是合法

因此后面数字填c\[i\]最小的

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int w;
    int c[10];
    
    signed main(){
    	cin>>w;
    	int mi=1e9;
    	for(int i=1;i<=9;i++){
    		cin>>c[i];
    		mi=min(mi,c[i]);
    	}
    	int num=w/mi;
    	int M=w;
    	for(int i=num;i>=1;i--){
    		for(int j=9;j>=1;j--){
    			if(M-c[j]>=mi*(i-1)){
    				M-=c[j];
    				cout<<j;
    				break;
    			}
    		}
    	}
    }

[E - Addition and Multiplication 2 _atcoder.jp]: https://atcoder.jp/contests/abc257/tasks/abc257_e
[eb69d8165d91431cb36e6fe32db03b89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/4b7c2ee762934d15bb15fc03d2bbf829.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关 Atcoder ABC 139E

Atcoder ABC 139E 题意: > n支球队大循环赛，每支队伍一天只能打一场，求最少几天能打完。解法： > 考虑抽象图论模型，既然一天只...

爱被打了一巴掌/ 2024年04月20日 10:31/ 0 赞/ 90 阅读

相关 ABC267 E - Erasing Vertices 2

一道DS好题！题意： ![804c8068f63a4b76865017f1a62cf33c.png][] ![dea11b8712d1472f83cdb1cf7198c

今天药忘吃喽~/ 2024年03月24日 15:46/ 0 赞/ 58 阅读

相关 ABC 238 D - AND and SUM

感觉有点难啊今天做了几道D，感觉除了DP都挺难的.... ![7977e156ab8f4d26b221ecde9ae0728a.png][] 思路：异或和加有一个性

傷城~/ 2024年03月24日 01:29/ 0 赞/ 93 阅读

相关【贪心】ABC257 E - Addition and Multiplication 2

暴力DP爆long long且T了显然是要按位贪心 [E - Addition and Multiplication 2 (atcoder.jp)][E - Additi

绝地灬酷狼/ 2024年03月23日 14:40/ 0 赞/ 71 阅读

相关 ABC247 E - Max Min

s b二分调 n m半天调不出来不写了，写不了一点直接贴别人代码算了题意： ![16d036c1f6324a3a9812f9a2fd2c4148.png][]

秒速五厘米/ 2024年03月23日 10:57/ 0 赞/ 79 阅读

相关【GCD+MST】ABC210 E

这道题告诉我们，一道题一定要去手摸样例，多造几个数据，然后找思路很多时候，题目看错了，码完发现思路错了，调半天调不出来，思路一直在旧框架打转，这些情况都是不去考察实际情况导

雨点打透心脏的1/2处/ 2024年03月17日 19:16/ 0 赞/ 81 阅读

相关【贪心+推式子计算贡献】ABC216 E

[E - Amusement Park (atcoder.jp)][E - Amusement Park _atcoder.jp] 题意： ![578018ad8dee42

妖狐艹你老母/ 2024年03月17日 16:02/ 0 赞/ 62 阅读

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 51 阅读

相关【数学】ABC 319 E

[E - Bus Stops][] 题意： ![f19239bed77b4ffda13a74736273c59e.png][] ![7d16c61674c24f709d8

朱雀/ 2024年03月04日 08:04/ 0 赞/ 110 阅读

相关 AtCoder ABC 128E Roadwork

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_e][https_atcoder.jp_contests_abc1

末蓝、/ 2021年11月01日 06:18/ 0 赞/ 281 阅读