codeforces 1428G Lucky Numbers (贪心+dp)

题目链接：https://codeforces.com/problemset/problem/1428/G1

仔细分析发现，贪心地选取 0,3,6,9 组成的数字一定是最优的，
而且这样的贪心策略，最多会有一个数字，不是全部由 0,3，6，9组成的

考虑按位分组dp，每组都有体积为：3,6,9 * 位权，价值为的物品
于是问题转变成了：先分组完全背包，每组物品中最多选 K 个，最后将每组合并，每组物品最多选 1 个
但时间复杂度为(O(NMK))，直接起飞
考虑优化：
对于完全背包最多取 K 个的限制，考虑将 K 二进制分组，将每种物品拆成按 K 的二进制分组组合的物品，
这样就转化成了 0/1 背包，复杂度为(O(NMlogK))

对于简单版，询问只有一次，考虑只选(K-1)个物品，枚举那个特殊的数字 x ，统计答案
还有个小性质:体积为6，9的物品都可以拆成为 3 的物品，就变成最多选 3*(k-1) 个物品了，必须这样优化，不然还是过不去

将各组物品合并时：
直接在每组内对该组进行背包更新答案，这样可以保证当前组物品不被重复选取

未使用小性质优化的代码(TLE)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 1000000;

int k,m,num,cntf,cntg;
int di[maxn];
ll n,F[10],f[21][maxn],g[maxn],v[1000],w[1000],vg[1000],wg[1000];

int qsm(int i,int po){
	int res = 1;
	while(po){
		if(po&1) res *= i;
		po >>= 1;
		i *= i;
	}
	return res;
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	num = 0;
	k = read();
	int K = k-1;
	int t = 0;
	while(K - (1<<t) > 0){ // 二进制分组 
		di[++num] = 1<<t;
		K -= (1<<t);
		++t;
	}
	di[++num] = K;
	for(register int i=0;i<6;++i) F[i] = read();
	m = read();
	
	n = read();
	
	memset(f,-1,sizeof(f));
	f[0][0] = 0;
	
	memset(g,0,sizeof(g));

	for(register int d=1;d<=6;++d){ //  dp 
		cntf = 0; cntg = 0;
		for(int j=1;j<=num;++j){
			v[++cntf] = 0, w[cntf] = 0;
		}
		
		for(register int i=1;i<=3;++i){
			ll wei = 1ll * (3*i) * qsm(10,d-1);
			ll val = 1ll * i * F[d-1];
			
			for(register int j=1;j<=num;++j){
				v[++cntf] = 1ll * di[j] * val;
				w[cntf] = 1ll * di[j] * wei;
			}
		}
		
		if(d>1) for(int i=0;i<=n;++i) f[0][i] = f[num][i];
		for(register int i=1;i<=cntf;++i){
			for(register int p=1;p<=num;++p){
				for(register int j=n;j>=w[i];--j){	
					if(f[p-1][j-w[i]] != -1) f[p][j] = max(f[p][j],f[p-1][j-w[i]] + v[i]);
				}
			}
		}
	}
	
    ll ans = 0;
	for(register int x=0;x<=n;x++){
		int tmp = x, o = 1;
		ll ta = 0;
		while(tmp > 0){
			if((tmp%10) % 3 == 0){
				ta += 1ll * (tmp % 10)/3 * F[o-1];
			}
			tmp /= 10;
			++o;
		}
		ans = max(ans,f[num][n-x]+ ta);
	}
	
	printf("%lld
",ans);
	
	return 0;
}

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 1000005;
const ll inf = (1LL << 58LL);

int k,m,num,cntf,cntg;
int di[maxn];
ll n,F[10],dp[maxn];

int qsm(int i,int po){
	int res = 1;
	while(po){
		if(po&1) res *= i;
		po >>= 1;
		i *= i;
	}
	return res;
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	num = 0;
	k = read();
	int K = k-1;
//	for(int i=1;i<=num;++i) printf("%d ",di[i]); printf("
");
	
	for(int i=0;i<6;++i) F[i] = read();
	m = read();
	
	n = read();
	fill(dp,dp+n+1,-1ll);
	dp[0] = 0; 
	for(int d=1;d<=6;++d){
		ll left = 3 * (k-1);
		ll group = 1;
		while(left > 0){
			group = min(group,left);
			ll wei = 1ll * group * qsm(10,d-1) * 3 ;
			ll val = 1ll *  group * F[d-1];
			
			for(int i=n; i>=wei; i--){
				if(dp[i-wei]!=-1ll) dp[i] = max(dp[i],dp[i-wei] + val);
			}
			left -= group;
			group *= 2;
		}
	}
	
    ll ans = 0;
	for(int x=0;x<=n;x++){
		int tmp = x, o = 1;
		ll ta = 0;
		while(tmp > 0){
			if((tmp%10) % 3 == 0){
				ta += 1ll * (tmp % 10)/3 * F[o-1];
			}
			tmp /= 10;
			++o;
		}
		if(dp[n-x]!=-1) ans = max(ans,dp[n-x]+ ta); //
	}
	
	printf("%lld
",ans);
	
	return 0;
}

对于加强版，由于有多组询问，不可以再枚举 x，
因为已经处理出前(K-1)个物品的 (DP) 表,按位考虑最后一个数字，更新 (DP) 表
注意最后更新的时候要更换枚举顺序，wei维在外，物品维在内，这样可以保证每组物品最多只选一个

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 1000010;
const ll inf = (1ll << 58ll);

int k,n,q;
int ten[10] = {1,10,100,1000,10000,100000};
ll F[7];
ll dp[maxn],g[maxn];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	k = read();
	for(int i=0;i<6;++i) F[i] = read();
	
	fill(dp,dp+1+999999,-inf);
//	for(int i=1;i<=10;++i) printf("%lld
",dp[i]);
	dp[0] = 0;
	
	for(int d=1;d<=6;++d){
		ll left = 1ll * 3 * (k-1);
		ll group = 1ll;
		
		while(left > 0){ // 二进制分组 
			group = min(group,left);
			
			ll val = 1ll * group * F[d-1];
			ll wei = 1ll * 3 * group * ten[d-1];
			
			for(int i=999999;i>=wei;--i){
				dp[i] = max(dp[i],dp[i-wei] + val);
			}
			left -= group;
			group *= 2;
		}
		
	}

	for(int d=1;d<=6;++d){
		for(int i=999999;i>=0;i--){
			for(int j=0;j<=9;++j){
				ll val, wei;
				if(j==3 || j==6 || j==9) val = 1ll * (j/3) * F[d-1];
				else val = 0;
				wei = 1ll * j * ten[d-1];
				
				if(wei > i) break;
				dp[i] = max(dp[i],dp[i-wei] + val);
			}
		}
		
	}	
	
	q = read();
	
	for(int i=1;i<=q;++i){
		n = read();
		printf("%lld
",dp[n]);
	}
	
	return 0;
}