题解：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)

，~~瓶颈在于读懂题目。~~

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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