题目
【测试限制】
【题目描述】
林老师是一位大理石收藏家，他在家里收藏了$N$块各种颜色的大理石，第$i$块大理石的颜色为$a_i$。
但是林老师觉得这些石头在家里随意摆放太过凌乱，他希望把所有颜色相同的石头放在一起。
换句话说，林老师需要对现有的大理石重新进行排列，在重新排列之后，对于每一个颜色$j$，如果最左边的颜色为$j$的大理石是第$l$块大理石，最右边的颜色为$j$的大理石是第$r$块大理石，那么从第$l$块大理石到第$r$块大理石，这些石头的颜色都为$j$。
由于这些大理石都比较重，林老师无法承受这些大理石的重量太久，所以他每次搬运只能交换相邻的两块大理石。
请问，林老师最少需要进行多少次搬运？
【输入格式】
第一行输入一个数字$N(2≤N≤4*10^5)$，表示大理石的总数。
第二行输入$N$个数字$a_1,a_2…,an(1≤a_i≤20)$表示第$i$块大理石的颜色为$a_i$。
【输出格式】
输出林老师最少需要搬运的次数。
【样例输入】
样例输入 1 7 3 4 2 3 4 2 2 样例输入 2 5 20 1 14 10 2 样例输入 3 13 5 5 4 4 3 5 7 6 5 4 4 6
【样例输出】
样例输出 1 3 样例输出 2 0 样例输出 3 21
【解题经历】
刚拿到这道题，我就被它的时间限制深深地吸引：$4000ms$？
那么长的时间限制肯定是暴搜穷竭搜索算法啊
于是推出了样例之后就开始码搜索...
打到后面发现自己连搜索都打不出来，于是这么一个伟大的算法就半路夭折了...
【正解&代码】
一道几乎可以说是模板的状压DP题。
观察所有的数据范围，发现$1≤a_i≤20$，而几乎是极端的对立，$2≤N≤4*10^5$，可以说对于$a_i$来说$N$是十分大了。
而时间限制又十分巨大：$4000ms$。
那么这又说明什么了吗？
在输入的数据中，若其中一两个的范围十分小，而其他数据又大得不正常
并且时间限制又异常宽松
对于时间来说，这道题的常数非常大（或者是某些模拟题）
对于空间来说，若用其他的空间来开数组是无法承受的
则说明这道题是状压DP，而且压缩的对象就是针对这些比较小的数的
那么，这道题的状态？
定义$dp$一维数组，其中对于$dp_i$，将$i$转换成二进制之后，对于其某一位，若这一位为一，说明这个状态中，第$i$种颜色已经全部被放在一起了
再定义$c$二维数组，其中$c_{ij}$表示在初始状态中，所有第$j$种颜色的石头前的第$i$种颜色的石头的个数
那么就有状转方程$$dp_i=dp_{i-(1<<j)}+cost(j)$$其中$j$为$i$的二进制下为一的位数
口胡还是太难了代码见下
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define cg (c=getchar()) 5 inline int qread(){ 6 int x,f=1;char c; 7 while(cg<'0'||'9'<c)if(c=='-')f=-1; 8 for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48)); 9 return x*f; 10 } 11 #undef cg 12 template<class T>inline T Max(const T x,const T y){return x>y?x:y;} 13 template<class T>inline T Min(const T x,const T y){return x<y?x:y;} 14 template<class T>inline T fab(const T x){return x>0?x:-x;} 15 const int MAXN=4e5; 16 const int INF=1ll<<60; 17 const int MAXA=25; 18 int a[MAXN+5],N,maxx; 19 int cnt[MAXA+5],c[MAXA+5][MAXA+5]; 20 int dp[(1<<20)+5]; 21 signed main(){ 22 N=qread(); 23 for(int i=1;i<=N;++i)maxx=Max(a[i]=qread(),maxx),--a[i]; 24 for(int i=1;i<=N;++i){ 25 ++cnt[a[i]]; 26 for(int j=0;j<=maxx;++j)c[j][a[i]]+=cnt[j]; 27 } 28 for(int i=0;i<=(1<<maxx)-1;++i)dp[i]=INF; 29 dp[0]=0; 30 for(int i=1;i<=(1<<maxx)-1;++i)for(int j=0;j<maxx;++j)if(i&(1<<j)){ 31 int cost=0,pre=i-(1<<j); 32 for(int k=0;k<maxx;++k)if(pre&(1<<k))cost+=c[j][k]; 33 dp[i]=Min(dp[i],dp[pre]+cost); 34 } 35 printf("%lld\n",dp[(1<<maxx)-1]); 36 return 0; 37 }