萝卜头IT论坛

了解更多
搜索
查看: 451|回复: 0
收起左侧

【算法题解】luogu P3694 邦邦的大合唱站队[状态压缩]

[复制链接]
发表于 2017-4-12 22:02:13 | 显示全部楼层 |阅读模式
题目地址:https://www.luogu.org/problem/show?pid=3694
大意:有一串无序数字,求最少让多少数字出列重新进入数列,使得数字串相同的数字排列在一起。




这题是luogu月赛的第一题...
这题用到了两个关键的思想
1.求ABCD全排列的最优组合。
可以先求AB,BA的最优;BC,CB的最优;AC,CA的最优,由此推出ABC的最优组合。
以(ABC)表示ABC中的最优排列,
写成记忆化搜索的就是求best(A(BCD),B,(ACD),C(ABD),D(BCD))。记忆化已经搜到的状态,下次用的时候不用计算。
写成DP的形式就是DP[(BCD)A]=MIN(DP[(BCD)A],DP[BCD]+OPT[A]);


2.这题状态20!种,用传统方法不好表示,那么就用位运算继续压缩
如,1111表示ABCD的最优组合,0111表示ABC的最优组合,0101表示AC,CA的最优组合
20个乐队就有1<<20-1种状态;
在DP种的应用为例。DP[0111]=MIN(DP[0111],DP[0101]+OPT[0010],DP[0011]+OPT[0100],DP[0110]+OPT[0001]...)


也就是本题的解法(状态转移方程写得不规范)
f[i+(1<<(j-1))]=min(f[i+(1<<(j-1))],f+size[j]-p[j][k+1]);


  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<cstring>
  4. using namespace std;
  5. typedef long long ll;
  6. const ll MX=1e5+5;
  7. ll size[MX]={0},a[MX]={0},p[22][MX]={0},f[1<<22]={0};
  8. ll n=0,m=0,c=0;
  9. int main()
  10. {
  11.         ios::sync_with_stdio(false);
  12.         cin>>n>>m;
  13.         for(int i=1;i<=n;i++)
  14.         {
  15.                 cin>>a[i];
  16.                 size[a[i]]++;
  17.         }
  18.         for(int i=1;i<=m;i++)
  19.         {
  20.                 int t=0;
  21.                 for(int j=1;j<=n;j++)
  22.                 {
  23.                         if(a[j]==i) t++;
  24.                         if(a[j-size[i]]==i&&j-size[i]>0) t--;
  25.                         if(j>=size[i]) p[i][j-size[i]+1]=t;
  26.                 }
  27.         }
  28.         c=(1<<m)-1;
  29.         memset(f,127,sizeof(f));
  30.         f[0]=0;
  31.         for(int i=0;i<=c;i++)
  32.         {
  33.                 ll k=0;
  34.                 for(int j=1;j<=m;j++)
  35.                 {
  36.                         if((1<<(j-1))&i) k+=size[j];
  37.                 }
  38.                 for(int j=1;j<=m;j++)
  39.                 {
  40.                         if(((1<<(j-1))&i)==0)
  41.                         {
  42.                                 f[i+(1<<(j-1))]=min(f[i+(1<<(j-1))],f[i]+size[j]-p[j][k+1]);
  43.                         }
  44.                 }
  45.         }
  46.         cout<<f[c];
  47. }
复制代码
AC代码
回复

使用道具 举报

联系站长|手机版|萝卜头IT论坛 ( 苏ICP备15050961号-1 )

GMT+8, 2018-4-24 08:44 , Processed in 0.099527 second(s), 26 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表