【算法题解】luogu P3694 邦邦的大合唱站队[状态压缩]
题目地址：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+OPT);
2.这题状态20！种，用传统方法不好表示，那么就用位运算继续压缩
如，1111表示ABCD的最优组合，0111表示ABC的最优组合，0101表示AC,CA的最优组合
20个乐队就有1<<20-1种状态；
在DP种的应用为例。DP=MIN(DP,DP+OPT,DP+OPT,DP+OPT...)
也就是本题的解法（状态转移方程写得不规范）
f=min(f,f+size-p);
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef long long ll;
const ll MX=1e5+5;
ll size={0},a={0},p={0},f={0};
ll n=0,m=0,c=0;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a;
size]++;
}
for(int i=1;i<=m;i++)
{
int t=0;
for(int j=1;j<=n;j++)
{
if(a==i) t++;
if(a]==i&&j-size>0) t--;
if(j>=size) p+1]=t;
}
}
c=(1<<m)-1;
memset(f,127,sizeof(f));
f=0;
for(int i=0;i<=c;i++)
{
ll k=0;
for(int j=1;j<=m;j++)
{
if((1<<(j-1))&i) k+=size;
}
for(int j=1;j<=m;j++)
{
if(((1<<(j-1))&i)==0)
{
f=min(f,f+size-p);
}
}
}
cout<<f;
}AC代码
大佬，f={0};是什么意思啊 dlh 发表于 2018-8-16 11:26
大佬，f
声明一个大小为4194304的数组f，并初始化为0 dlh 发表于 2018-8-16 11:26
大佬，f
1<<22的意思是二进制1左移22位，即十进制4194304 dlh 发表于 2018-8-16 11:26
大佬，f
但是由于是状压DP，用二进制可以完整循环所有的状态并且判重 这个显卡不太冷 发表于 2018-8-22 02:26
但是由于是状压DP，用二进制可以完整循环所有的状态并且判重
666啊！！ 这个显卡不太冷 发表于 2018-8-22 02:26
但是由于是状压DP，用二进制可以完整循环所有的状态并且判重
我还是define吧 看不懂 很是深奥啊
页:
[1]