状压dp的递推顺序
状压dp的顺序并非从左到右
而是从 状态中少1 到 状态中多1
且要枚举状态中最后一位1出现的位置
st_比st少一位1，其余位一样，那么st_一定在其之前出现过（被枚举过）
#include<bits/stdc++.h>
using namespace std;
int const N=1e5+7;
int const M=27;
int n,m;
int num[M],sum[N][M];
int f[1<<21];
int main(){
cin >> n >> m;
for(int i=1,x;i<=n;++i){
cin >> x;x--;
num[x]++;
for(int j=0;j<m;++j) sum[i][j]=sum[i-1][j];
sum[i][x]++;
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<(1<<m);++i){
int s=0;
for(int j=0;j<m;++j){
if((i>>j)&1) s+=num[j];
}
for(int j=0;j<m;++j){
if((i>>j)&1) {
int l=s-num[j];
int r=s;
f[i]=min(f[i],f[i^(1<<j)]+num[j]-(sum[r][j]-sum[l][j]));
}
}
}
cout << f[(1<<m)-1];
return 0;
}
查看13道真题和解析