[loj2977]巧克力

先考虑第一个问题，即求最小的巧克力块数

将这张网格图建图（仅对$c_{i,j}\ne -1$的位置建点），即求点数最少的连通块（的点数）使得存在$k$个不同的$c_{i,j}$

（以下$c$仅用一维数组表示，$c_{i}$即表示编号为$i$的点的原来的$c_{i,j}$）

令$f_{i,S}$表示包含$i$且集合$S$中的$c_{i}$都在连通块中出现（仅要求出现，不要求其余点不出现）的点数最少的连通块（的点数），显然只需要求出这个dp数组即可，下面考虑如何求：

初始令$f_{i,0}=f_{i,\{c_{i}\}}=1$且$f_{i,j}=\infty$（其中$j>0$），之后不断利用以下几个递推式进行转移——
$$
S'\ne \empty且S'\subset S,f_{i,S}=\min(f_{i,S},f_{i,S'}+f_{i,S\setminus S'}-1)\\(i,j)\in E,f_{i,S}=\min(f_{i,S},f_{j,S}+1)
$$
换言之，只需要不断将其以此法进行修改直至无法修改即得到了正确的$f_{i,j}$，此做法正确性显然

虽然整体没转移有后效性，但第一个转移在$S$这一维上一定是从$S_{sub}$转移到$S$（其中$S_{sub}\subset S$），换言之若从小到大枚举$S$那么就可以从小到大枚举$S$，并求出对应的$f_{i,S}$（最终的值），那么一定是从前面转移

再用枚举子集的技巧优化，可以做到总计$o(n3^{C})$的复杂度（其中$C=\max c_{i}$）

更进一步的，第3个转移是一个最短路的形式（直接从dijkstra的角度来说，即对于最小的$f_{i,S}$具有后效性），当求完后再求一次类似最短路的过程即可

这里转移的复杂度是$o(n\log n\ 2^{C})$，在$C$较小时可以通过

（上面所述的也就是所谓的“斯坦纳树”，反正就是一个此类状压dp的计算方式）

当$C$较大时，上面的做法显然不行，但如果将这些$c_{i}$随机映射到$[1,k]$上（即令$C=k$），得到的解显然也是合法的（但并不一定最小）

考虑点数最小的答案是其中的某$k$个，那么只需要这$k$个中任意两个不映射到同一个位置上即可，这样的概率即为$\frac{k!}{k^{k}}$，若取$k=5$大约为0.0384

以此法做大约200次，求最小值即可得到一个较为准确的答案

另外还有需要最小化中位数，可以二分中位数$mid$，并将所有数分为0和1（小于等于$mid$或大于$mid$），在上面的状态基础上再定义一个$g_{i,S}$表示在$f_{i,S}$最小的基础上最少的1的个数即可

总复杂度为$o(TC\log A(n\log n\ 2^{k}+n3^{k}))$（其中$C=200$即操作次数，$A=\max a_{i,j}$），略卡常数

（另外测评时注意跳过样例，否则会Judgment Failed）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 250

  4 #define oo 0x3f3f3f3f

  5 #define pii pair<int,int>

  6 #define mp make_pair

  7 #define fi first

  8 #define se second

  9 struct Edge{

 10     int nex,to;

 11 }edge[N<<2];

 12 priority_queue<pair<pii,int> >q;

 13 int V,E,t,n,m,k,id[N][N],c[N][N],val[N],vis[N],head[N],a[N];

 14 pii ans,b[N],f[N][32];

 15 pii add(pii x,pii y){

 16     return mp(x.fi+y.fi,x.se+y.se);

 17 }

 18 pii neg(pii x){

 19     return mp(-x.fi,-x.se);

 20 }

 21 void add(int x,int y){

 22     edge[E].nex=head[x];

 23     edge[E].to=y;

 24     head[x]=E++;

 25 }

 26 void dijkstra(int S){

 27     memset(vis,0,sizeof(vis));

 28     for(int i=1;i<=V;i++)q.push(mp(neg(f[i][S]),i));

 29     while (!q.empty()){

 30         int k=q.top().second;

 31         q.pop();

 32         if (vis[k])continue;

 33         vis[k]=1;

 34         for(int i=head[k];i!=-1;i=edge[i].nex)

 35             if (f[edge[i].to][S]>add(f[k][S],b[edge[i].to])){

 36                 f[edge[i].to][S]=add(f[k][S],b[edge[i].to]);

 37                 q.push(mp(neg(f[edge[i].to][S]),edge[i].to));

 38             }

 39     }

 40 }

 41 pii calc(int mid){

 42     for(int i=1;i<=V;i++)

 43         if (val[i]<=mid)b[i]=mp(1,0);

 44         else b[i]=mp(1,1);

 45     for(int i=1;i<=V;i++){

 46         for(int j=1;j<(1<<k);j++)f[i][j]=mp(oo,0);

 47         f[i][0]=f[i][(1<<a[i])]=b[i];

 48     }

 49     for(int i=1;i<(1<<k);i++){

 50         for(int j=1;j<=V;j++)

 51             for(int s=(i&(i-1));s;s=(i&(s-1)))f[j][i]=min(f[j][i],add(add(f[j][s],f[j][i^s]),neg(b[j])));

 52         dijkstra(i);

 53     }

 54     pii ans=mp(oo,0);

 55     for(int i=1;i<=V;i++)ans=min(ans,f[i][(1<<k)-1]);

 56     return ans;

 57 }

 58 pii calc(){

 59     int l=0,r=1e6,ans=calc(0).fi;

 60     while (l<r){

 61         int mid=(l+r>>1);

 62         if (calc(mid).se<=ans/2)r=mid;

 63         else l=mid+1;

 64     }

 65     return mp(ans,l);

 66 }

 67 int main(){

 68     srand(time(0));

 69     scanf("%d",&t);

 70     while (t--){

 71         scanf("%d%d%d",&n,&m,&k);

 72         for(int i=1;i<=n;i++)

 73             for(int j=1;j<=m;j++)scanf("%d",&c[i][j]);

 74         V=E=0;

 75         memset(head,-1,sizeof(head));

 76         memset(id,0,sizeof(id));

 77         for(int i=1;i<=n;i++)

 78             for(int j=1;j<=m;j++){

 79                 if (c[i][j]>0){

 80                     id[i][j]=++V;

 81                     scanf("%d",&val[V]);

 82                     if ((i>1)&&(id[i-1][j])){

 83                         add(id[i-1][j],id[i][j]);

 84                         add(id[i][j],id[i-1][j]);

 85                     }

 86                     if ((j>1)&&(id[i][j-1])){

 87                         add(id[i][j-1],id[i][j]);

 88                         add(id[i][j],id[i][j-1]);

 89                     }

 90                 }

 91                 else scanf("%*d");

 92             }

 93         ans=mp(oo,0);

 94         for(int times=0;times<200;times++){

 95             memset(vis,-1,sizeof(vis));

 96             for(int i=1;i<=n;i++)

 97                 for(int j=1;j<=m;j++)

 98                     if (c[i][j]>0){

 99                         if (vis[c[i][j]]<0)vis[c[i][j]]=rand()%k;

100                         a[id[i][j]]=vis[c[i][j]];

101                     }

102             ans=min(ans,calc());

103         }

104         if (ans.fi==oo)printf("-1 -1\n");

105         else printf("%d %d\n",ans.fi,ans.se);

106     }

107 }

巴特西

[loj2977]巧克力

最新文章

热门文章