雑すぎた。
http://codeforces.com/contest/758/problem/D
問題
整数Nと数字から構成された文字列Sが与えられる。
Sを分割し、いくつかのN以下の整数となるようにする。
そうして得られたいくつかの整数を、N進数の各桁の値とみなし、その値を改めて10進数表記に直す、という手順を考える。
得られる値の最小値を求めよ。
解法
以下の状態を考える。
f(i) := Sの先頭i文字に関し、問題の手順で得られる値の最小値
以下の要領でf(i)をDPで順次もとめていけばよい。
途中で10^18を超えるケースに注意。
f(i+x) = min(f(i)*N + int(S[(i+1)..(i+x)]))
ll N,L; string S; ll dp[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; L=S.size(); FOR(i,L+5) dp[i]=1LL<<60; dp[0]=0; FOR(i,L) if(dp[i]<1LL<<60) { ll a=0; for(x=i;x<L;x++) { a=a*10+S[x]-'0'; if(a>=N) break; if(dp[i]*N/N == dp[i]) dp[x+1]=min(dp[x+1],dp[i]*N+a); if(S[i]=='0') break; } } cout<<dp[L]<<endl; }
まとめ
計算量的にはもっと桁数多くてもよさそうだけど、10^18の制限があるから抑えたのかな。