初手が思いつけば答えはすぐ。
https://yukicoder.me/problems/no/2039
問題
初期状態で2変数X=Y=1である。
以下の処理を任意に繰り返し、X=Nとしたい。
- XにYを加える。コストがAかかる。
- YをXで上書きする。コストがBかかる。
加えて、途中Xの値として経由していはいけない値がいくつか与えられる。
条件を満たす最小総コストを求めよ。
解法
後者を行うのは、XがNの約数の時だけである。
よってNの約数を列挙し、DPの要領でXがそれらの各値に至る最小コストを求めよう。
int N,M,A,B; int C[5050]; int NG[5050]; ll dp[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>A>>B; vector<int> V; for(i=1;i*i<=N;i++) if(N%i==0) { V.push_back(i); if(i*i!=N) V.push_back(N/i); } sort(ALL(V)); FOR(i,M) cin>>NG[i]; FOR(i,V.size()) dp[i]=1LL<<60; dp[0]=0; FOR(i,V.size()) { int mi=N+1; FOR(j,M) if(NG[j]%V[i]==0) mi=min(mi,NG[j]); for(j=i+1;j<V.size();j++) if(V[j]<mi&&V[j]%V[i]==0) { x=V[j]/V[i]; dp[j]=min(dp[j],dp[i]+1LL*(x-1)*A+B); } } if(dp[V.size()-1]>=1LL<<60) { cout<<-1<<endl; } else { cout<<dp[V.size()-1]-B<<endl; } }
まとめ
これは割とすんなり。