CFR 71 C. Round Table Knights ( Cycle DP )

Problem - C - Codeforces

題意：
在一個桌子上，有 N 個武士兩兩相鄰等弧距坐著。每個武士都有心情好壞，求是否有一種武士的組合，滿足所有武士心情都好，且相鄰連接後是一個正多邊形( 同角同長度 )。

數據範圍：
武士人數 3 ≤ N ≤ 1e5

解法：
顯然要檢查的只有 N 的因數邊的正多邊形。因此最多只有 O( sqrt( N ) ) 個情形要檢查。如果檢查的複雜度是 O( N )，問題就能解決。又注意到是環的問題，可以拆掉並順時針簡化成序列，接一個自己在自己後面，轉為在這個兩倍原環長度的序列上看這個環。
對於每個枚舉中的邊長 x：
dp[ i ] : i 號武士 ( 若 i >= N, 則是 i - N 號 ) 逆時針最多可以和幾個心情好的武士，連續且相鄰兩兩間隔距離 x 進行連線。
dp[ i ] = ( i 好武士心情好 ) ? max{ 1, dp[ i - x ] } : 0
動態規劃程序結束後，如果有某個 dp值不少於所要邊長，便一定滿足。

時間 / 空間複雜度：
O( N ^ 1.5 ) / O( N )

int N;
vi A; // good mood;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi gm2; // good mood table * 2

void preprocess(){
    gm2 = vi( N << 1 );
    for( int i = 0; i < 2 * N; ++i )
        gm2[ i ] = i < N ? A[ i ] : A[ i - N ];
}

void solve(){
    for( int i = 1; i * i <= N; ++i ){
        if( not ( N % i == 0 ) )
            continue;
        if( not ( N / i > 2 ) )
            continue;

        vi dp( N << 1 );
        for( int j = 0; j < N; ++j )
            dp[ j ] = gm2[ j ];
        for( int j = 0; j < N << 1; ++j )
            if( gm2[ j ] and j + i < N << 1 and gm2[ j + i ] )
                upmax( dp[ j + i ], dp[ j ] + 1 );

        if( *max_element( dp.begin(), dp.end() ) >= N / i )
            cout << "YES" << endl,
            exit( 0 );
        
        if( not ( i > 2 ) ) // otherwise not polygon
            continue;

        dp = vi( N << 1 );
        for( int j = 0; j < N; ++j )
            dp[ j ] = gm2[ j ];
        for( int j = 0; j < N << 1; ++j )
            if( gm2[ j ] and j + N / i < N << 1 and gm2[ j + N / i ] )
                upmax( dp[ j + N / i ], dp[ j ] + 1 );

        if( *max_element( dp.begin(), dp.end() ) >= i )
            cout << "YES" << endl,
            exit( 0 );
    }
    cout << "NO" << endl;
}