|
|
题目地址：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[i]+size[j]-p[j][k+1]);
- #include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef long long ll;
const ll MX=1e5+5;
ll size[MX]={0},a[MX]={0},p[22][MX]={0},f[1<<22]={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[i];
size[a[i]]++;
}
for(int i=1;i<=m;i++)
{
int t=0;
for(int j=1;j<=n;j++)
{
if(a[j]==i) t++;
if(a[j-size[i]]==i&&j-size[i]>0) t--;
if(j>=size[i]) p[i][j-size[i]+1]=t;
}
}
c=(1<<m)-1;
memset(f,127,sizeof(f));
f[0]=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[j];
}
for(int j=1;j<=m;j++)
{
if(((1<<(j-1))&i)==0)
{
f[i+(1<<(j-1))]=min(f[i+(1<<(j-1))],f[i]+size[j]-p[j][k+1]);
}
}
}
cout<<f[c];
}
|
有人找乐子，有人照镜子
|
发表于 2017-4-12 22:02:13
发表于 2018-8-16 11:26:05
