SRM493 Div1 Medium(450) AmoebaCode
動的計画法。何個か前までの数字を組み合わせごとに最小の距離を覚えておく。答えはK以下なので、K-1個前までに数字が出てこなければK個前に数字が出てきたとみなして構わない。↓のdのループをd<=Kから、d<P[j]にしたら間に合うようになった。P[j]の値が大きくなるjはそんなに多くない。
#include <string> #include <vector> #include <algorithm> using namespace std; class AmoebaCode{public: int find( string code, int K ) { int n = (int)code.size(); vector<int> E(K,1); // K^i for ( int i=1; i<K; i++ ) E[i] = E[i-1]*K; vector<int> T(E[K-1],K); for ( int i=0; i<n; i++ ) { vector<int> P = T; T = vector<int>(E[K-1],0); int k1 = code[i]=='0' ? 1 : code[i]-'0'; int k2 = code[i]=='0' ? K : code[i]-'0'; for ( int j=0; j<E[K-1]; j++ ) for ( int k=k1; k<=k2; k++ ) { int t = j*K%E[K-1]+k-1; int d; for ( d=1; d<P[j]; d++ ) if ( j/E[d-1]%K == k-1 ) break; T[t] = max(T[t],d); } } return *max_element(T.begin(),T.end()); }};