なんとか思い出せてよかった。
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; }
まとめ
なんか似たようなの見たことあるような気もする。