题解：P14406 [JOISC 2015] 愉快的标志设计 / En-JOI-able Logo Design

· · 题解

头一次见把解题过程写在题面里的题目。

思路

破环为链后倍长，考虑对于每个位置作为开头进行计算。

然后你发现对于一个 k，你直接预处理 J、O、I 的前缀出现次数，就能够把一个 k 级序列归约到一个 k-1 级别序列的问题上。

设 f_{i,k} 表示从第 i 个位置开始构成一个 k 级别的序列所需要的最小代价，递推是显然的，可以从 f_{i+3\times4^{k-1},k-1} 直接推得。

然后你发现 k\le 10，这题就做完了。

真是何意味，时间复杂度 O(k4^k)，瓶颈在于读懂题目。

代码

:::success[代码]

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int
using namespace std;
const ll N=(1<<21)+10;
const ll INF=2147483647; 
ll k,f[N][11],suma[N],sumb[N],sumc[N];
string s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>k>>s;s=' '+s+s;
    ll n=(1<<(2*k));
    for(ll i=1;i<=2*n;i++){
        f[i][0]=0;
        suma[i]=suma[i-1]+(s[i]=='J');
        sumb[i]=sumb[i-1]+(s[i]=='O');
        sumc[i]=sumc[i-1]+(s[i]=='I');
    }
    for(ll i=2*n;i;i--){
        for(ll j=1;j<=k;j++){
            if(i+(1<<(j*2))-1>2*n) break;
            f[i][j]=f[i+3*(1<<((j-1)*2))][j-1];
            f[i][j]+=(1<<(2*(j-1)))-suma[i+(1<<(2*(j-1)))-1]+suma[i-1];
            f[i][j]+=(1<<(2*(j-1)))-sumb[i+2*(1<<(2*(j-1)))-1]+sumb[i+(1<<(2*(j-1)))-1];
            f[i][j]+=(1<<(2*(j-1)))-sumc[i+3*(1<<(2*(j-1)))-1]+sumc[i+2*(1<<(2*(j-1)))-1];
        }
    }
    ll ans=INF;
    for(ll i=1;i<=n;i++) ans=min(ans,f[i][k]);
    cout<<ans;
    return 0;
}

:::