Codeforces Raif Round 1 : G2. Lucky Numbers (Hard Version)

そういやこんな問題もあったな。
https://codeforces.com/contest/1428/problem/G2

問題

正整数Nが与えられるので、K個の非負整数の和でNを表現したい。
この際、各整数に3,6,9が含まれていると、その桁に応じてスコアが与えられる。
Nに対する総スコアの最大値を求めよ。

解法

各桁についてみると、0,3,6,9でない値は何も得がないので、高々1か所しか使わないようにしたい。
そこで、各桁、0～3(K-1)箇所まで3を使える、と考えてナップサック問題を解き、
f(n) := 0,3だけからなる整数を3(K-1)個使って合計をnにするときに総スコアの最大値
となるf(n)を埋めよう。

その際、ナップサック問題で愚直に3(K-1)回3を使うかどうか判定するとO(NK)かかってTLEする。
そこで、1回使う・2回使う…・2^m回使う、とO(log(K))個の塊に分割して考えるとよい。

最後に、残った1個の値を埋める。
g(n) := 0,3だけからなる整数を各桁3(K-1)個と、あと任意の非負整数を1つ使って合計をnにするときに総スコアの最大値
これはf(n)から初めて、各桁0～9を埋めた場合を考えるとよい。

int K;
ll F[6];
int Q;
int N;

ll dp[1010101];
ll p10[8];
int FS[10]={0,0,0,1,0,0,2,0,0,3};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,6) p10[i+1]=p10[i]*10;
	
	cin>>K;
	FOR(i,6) cin>>F[i];
	
	FOR(i,1000001) dp[i]=-1LL<<60;
	dp[0]=0;
	FOR(i,6) {
		int cand=3*(K-1);
		int cur=1;
		while(cand) {
			int num=min(cand,cur);
			
			ll sc=num*F[i];
			ll v=num*3*p10[i];
			for(j=999999;j>=v;j--) dp[j]=max(dp[j],dp[j-v]+sc);
			cand-=num;
			cur*=2;
		}
	}
	
	FOR(i,6) {
		for(j=999999;j>=0;j--) {
			for(x=1;x<=9;x++) if(j>=x*p10[i]) dp[j]=max(dp[j],dp[j-x*p10[i]]+FS[x]*F[i]);
		}
	}
	
	
	
	cin>>Q;
	while(Q--) {
		cin>>N;
		cout<<dp[N]<<endl;
	}
	
}

まとめ

言われてみると割とシンプルなんだよな。