SRM493 Div1 Medium(450) AmoebaCode

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()); 
}};