题解 P3943 【星空】

T_Q_X · 2020-10-21 12:31:03 · 题解

题目链接

传送门

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