|
|
题目地址：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]);
- #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
