【贪心】ABC257 E - Addition and Multiplication 2

暴力DP爆long long且T了

显然是要按位贪心

E - Addition and Multiplication 2 (atcoder.jp)

题意：

思路：

一开始想的是暴力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;
			}
		}
	}
}