kmjp's blog

競技プログラミング参加記です

yukicoder : No.1782 ManyCoins

なんとか思い出せてよかった。
https://yukicoder.me/problems/no/1782

問題

N種類の硬貨があり、それぞれの価値が与えられる。
各硬貨が無限にある場合、1~Lのうち効果の組み合わせで表現できる価値は何通りか。

解法

硬貨のうち最大の価値をWとする。
dp(w) := 硬貨の組み合わせの価値をWで割った余りをwにできる組み合わせのうち、価値の最小値
とする。
各wに対し、(dp(w)+kW)の形の価値を表現できることは明らか。
dp(w)はW点NW辺の有向グラフに対するダイクストラ法で求めることができる。

int N;
ll L;
ll W[22];
ll dp[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>W[i];
	sort(W,W+N);
	
	ll M=W[N-1];
	
	FOR(i,1000000) dp[i]=1LL<<60;
	dp[0]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	
	while(Q.size()) {
		ll c=-Q.top().first;
		ll a=Q.top().second;
		Q.pop();
		if(dp[a]!=c) continue;
		FOR(i,N-1) {
			ll v=c+W[i];
			if(dp[v%M]>v) {
				dp[v%M]=v;
				Q.push({-v,v%M});
			}
		}
	}
	
	ll ret=-1;
	FOR(i,M) {
		if(dp[i]<=L) {
			ret+=(L-dp[i])/M+1;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

なんか似たようなの見たことあるような気もする。