题解 P3943 【星空】

· · 题解

关于转换的部分，题解和下面的人其实讲的已经很清楚了，不过我想纠正一下下面的人一点，原题解说是bfs是没有问题的，因为每次更新的代价是1，你访问到一个点了，下次它再被更新肯定没有当前优，所以是O(n)的bfs。

还有就是希望不要有人像我一样，交了十几次，最后发现是K和M的输入搞反了。。。

我用的和原题解的方法一样，就是差分+状压+bfs(话说这是我第一次看到差分的拓展。。。)

然后我在程序里面注解了一下。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define maxn 40009
#define maxx 1000000000
using namespace std;
int n,m,k,x,val[maxn],have[maxn],w[maxn],d[maxn],dis[20][20],dp[500009];
bool in[maxn];
queue<pair<int,int> >q;
int main()
{
  scanf("%d%d%d",&n,&k,&m);
  for (int i=0;i<=n+1;i++) val[i]=1;
  for (int i=1;i<=k;i++) 
  {
   scanf("%d",&x); val[x]=0;
  }
  k=0;
  for (int i=1;i<=n+1;i++)
  if (val[i]^val[i-1]) {have[i]=++k,w[k]=i;}//cout<<"!"<<i<<endl;}
  for (int i=1;i<=m;i++) scanf("%d",&d[i]),d[i]++;
  pair<int,int>now;int to;
  for (int i=1;i<=k;i++)
  for (int j=1;j<=k;j++)
  if (i!=j) dis[i][j]=maxx;
//一个个入队列，做一遍bfs，时间复杂度为O(kn)  
 for (int i=1;i<=k;i++)
  {
      for (int j=0;j<=n+1;j++) in[j]=false;
      q.push(make_pair(w[i],0)); in[w[i]]=true;
      while (!q.empty())
      {
        now=q.front();q.pop();
        for (int j=1;j<=m;j++)
      {
          to=now.first+d[j]-1;
          if ((to>n+1)||(in[to])) continue;
          q.push(make_pair(to,now.second+1));in[to]=true;
          if (have[to]) dis[i][have[to]]=now.second+1;
      }
      for (int j=1;j<=m;j++)
      {
        to=now.first-d[j]+1;
          if ((to<0)||(in[to])) continue;
          q.push(make_pair(to,now.second+1));in[to]=true;
          if (have[to]) dis[i][have[to]]=now.second+1;
      }
    }
  }
  for (int i=1;i<(1<<k);i++) dp[i]=maxx;
//就是选择当前状态下还没消除的两个点，将它们消掉的状态更新，不过和noip提高组2016Day2T3的愤怒的小鸟很像，反正当前状态下第一个
//物品肯定是要消的，那不如就直接选择第一个没被消的点来更新。
  for (int i=0;i<(1<<k);i++)
  {
      int j=0;
    while (i&(1<<j)) j++;
    for (int p=j+1;p<k;p++)
    if (!(i&(1<<p)))
    dp[i|(1<<j)|(1<<p)]=min(dp[i|(1<<j)|(1<<p)],dp[i]+dis[j+1][p+1]);    
  } 
  printf("%d\n",dp[(1<<k)-1]);
  return 0;
}