洛谷P3943 星空

题目链接

传送门

solution

挺考验思维的一道题，考场上猜了各种假贪心居然水过了32分
考虑这道题目中困扰我们的地方：

• 1.对区间取反
  容易想到用差分思想，\(p[i]\)维护第原序列第\(i-1\)个点状态与第\(i\)个点异或的结果，即可将区间\([l,r]\)取反转化为仅对\(p[l]\)与\(p[r+1]\)取反
• 2.有多种取反方式
  事实上，对一段区间\([l,r]\)取反，若\(p[l]\)与\(p[r+1]\)均为1，那么它们都会变成0，相当于相互抵消，若其中一个是1，相当于将1移动到0的位置，(\(p[l]\)与\(p[r-1]\)都是1的情况???)那么抵消任意2个0的最小步数，就是将他们移动到一起的最小步数，每个点所能移动到的距离，就是题目中给出的不同取反长度。于是我们可以\(O(n,m)\)求出任意1个1移动到任意位置需要的最小步数。于是题目就转化为了有若干个点，任意2个点之间可以花费一定代价相互抵消，问将所有节点抵消的最小代价。
• 原序列中每一个1最多导致现在的问题中多出2个点，于是最多有16个点，状压DP即可

code

#include<bits/stdc++.h>
using namespace std;
const int N=80010;
int n,k,m,t[N],b[N],dis[N],dp[N],p[N],cnt,sum;
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=k;++i){
		int x;scanf("%d",&x);
		t[x]^=1;t[x+1]^=1;
	} 
	for(int i=1;i<=n+1;++i) if(t[i]) p[cnt++]=i;
	sum=(1<<cnt);
	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
	memset(dis,0x3f,sizeof(dis));dis[0]=0;
	for(int i=1;i<=m;++i)
		for(int j=b[i];j<=n;++j)
			dis[j]=min(dis[j],dis[j-b[i]]+1);
	for(int i=1;i<=m;++i)
		for(int j=n-b[i];j>=0;--j) 
			dis[j]=min(dis[j],dis[j+b[i]]+1);
	memset(dp,0x3f,sizeof(dp));dp[0]=0;
	for(int i=0;i<sum;++i)
		for(int j=0;j<cnt;++j) if(!(i&(1<<j)))
			for(int k=j+1;k<cnt;++k)
				if(!(i&(1<<k))) dp[i^(1<<j)^(1<<k)]=min(dp[i^(1<<j)^(1<<k)],dp[i]+dis[p[k]-p[j]]);
	printf("%d\n",dp[sum-1]);
	return 0;
}