kmjp's blog

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

yukicoder : No.2039 Copy and Avoid

初手が思いつけば答えはすぐ。
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;
	}
}

まとめ

これは割とすんなり。