正题

题目链接:https://jzoj.net/senior/#main/show/3853

---

题目大意

$n$n个数字，每次可以将一个数字拿出并插入任意位置，操作$k$k次求最少段连续相同的数。

---

解题思路

先将相同的缩在一起
设$f_{i,j,s,z}$fi,j,s,z​表示到第$i$i个，拿出了$j$j个，然后前面有的数集合为$s$s，最后一个数字是$z$z。

定义目前的数字是$x$x，加上$x$x之后的集合是$zs$zs

然后我们分情况考虑

1. 不拿出这个$f_{i,j,zs,x}=min\{f_{i-1,j,s,z}+[z!=x]\}$fi,j,zs,x​=min{fi−1,j,s,z​+[z!=x]}
2. 拿出这个，放到前面$f_{i,j+v_i,zs,z}=min\{f_{i-1,j,s,z}+!((s>>x)\&1)\}$fi,j+vi​,zs,z​=min{fi−1,j,s,z​+!((s>>x)&1)}
3. 拿出这个，放到后面(要预处理后面是否还有这个才可以放)$f_{i,j+v_i,s,z}=min\{f_{i-1,j,s,z}\}$fi,j+vi​,s,z​=min{fi−1,j,s,z​}

时间复杂度$O(nk2^8*8)$O(nk28∗8)

---

$code$code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m,k,f[N][N][280][10],ans,a[N],v[N];
bool zk[N][10];
int main()
{
	scanf("%d%d",&m,&k);
	a[0]=-1;
	for(int i=1;i<=m;i++){
		int x;scanf("%d",&x);
		x-=25;
		if(x!=a[n])a[++n]=x,v[n]=1;
		else v[n]++;
	}
	for(int i=n;i>=1;i--)
		for(int z=0;z<8;z++)
			zk[i][z]=zk[i+1][z]|(a[i]==z);
	memset(f,0x3f,sizeof(f));
	f[0][0][0][8]=0;
	for(int i=1;i<=n;i++){
		int x=a[i];
		for(int j=0;j<=k;j++)
			for(int s=0;s<256;s++)
				for(int z=0;z<9;z++){
					int zs=s|(1<<x);
					f[i][j][zs][x]=min(f[i][j][zs][x],f[i-1][j][s][z]+(x!=z));
					if(j+v[i]<=k){
						if(zk[i+1][x])f[i][j+v[i]][s][z]=min(f[i][j+v[i]][s][z],f[i-1][j][s][z]);
						f[i][j+v[i]][zs][z]=min(f[i][j+v[i]][zs][z],f[i-1][j][s][z]+!((s>>x)&1));
					}
				}
	}
	ans=2147483647;
	for(int s=0;s<256;s++)
		for(int z=0;z<=8;z++)
			ans=min(ans,f[n][k][s][z]);
	printf("%d",ans);
}

• 点赞
• 收藏
• 分享
• • 文章举报

ssl_wyc 发布了848 篇原创文章 · 获赞 55 · 访问量 8万+ 他的留言板 关注