Codeforces Round #585 (Div. 2)E（状态压缩DP，思维）

#define HAVE_STRUCT_TIMESPEC

#include<bits/stdc++.h>
using namespace std;
long long n,x;
long long num[21],f[1<<20],g[21][21];
int main(){
cin>>n;
for(;n--;){
cin>>x;
++num[--x];//计数--x出现的次数
for(int i=0;i<20;++i)//将x全部放置在相对位置i前面
g[x][i]+=num[i];//num[i]为x前面颜色i的个数
}
for(int i=1;i<1<<20;++i)
f[i]=1e18;
//memset(f,1,sizeof(f));//全部初始为一个很大的值
//f[0]=0;
for(int i=0;i<1<<20;++i)//遍历每一种排列
for(int j=0;j<20;++j)//遍历在i前面的颜色j
if(!(i>>j&1)){//i中如果已经有j就不需要计算了
long long tmp=f[i];//排好i序列的次数
for(int k=0;k<20;++k)
if(i>>k&1)//哪一位上已经排好
tmp+=g[j][k];//加上把j排在k前面的次数
f[i|(1<<j)]=min(f[i|(1<<j)],tmp);//更新把j排在i前面序列的最小值
}
cout<<f[(1<<20)-1];
}

/*#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[400007];
int c[400007];
long long f[(1<<20)+7];
long long dp[(1<<20)+7][27];
int cnt[27];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
c[i]=a[i];
}
sort(c+1,c+1+n);//将a数组复制到c并排序
int m=unique(c+1,c+1+n)-c-1;//找出c数组中不同元素的个数
for(int i=1;i<=n;++i)
a[i]=lower_bound(c+1,c+1+m,a[i])-c;//将a数组改成原本元素最早出现的位置
for(int i=1;i<=n;++i){
++cnt[a[i]];//计数最早出现在该位置元素的个数
for(int j=1;j<=m;++j){
if(!cnt[j]||j==a[i])
continue;
dp[1<<(j-1)][a[i]]+=cnt[j];//出现在a[i]以前的a[j]的个数（将a[i]原本的存放的颜色全部移动到a[j]原本存放的颜色以前所作出的贡献）
}
}
for(int i=0;i<1<<m;++i)
for(int j=1;j<=m;++j)
dp[i][j]=dp[i&(-i)][j]+dp[i^(i&(-i))][j];//将i中位上为1的颜色全部移动到到j颜色之前的贡献等于i去掉最后一位为1的序列的贡献加上i最后一位为1的贡献
memset(f,127/3,sizeof(f)),f[0]=0;
for(int i=0;i<1<<m;++i){
if(f[i]==f[1<<m])
continue;
for(int j=0;j<m;++j)
if(!(i>>j&1))//如果i向右移动j位是偶数（最后一位是0），说明中间有颜色没有移动到它应该的位置上
f[i|(1<<j)]=min(f[i]+dp[i][j+1],f[i|(1<<j)]);//将从右向左j位上的0补成1，它的贡献为自身和f[i]+dp[i][j+1]的最小值（i序列的贡献加上把i序列全部移动到j+1颜色以前的贡献）
}
cout<<f[(1<<m)-1]<<endl;//全部排列为1的贡献就是题意排列的答案
return 0;
}*/

巴特西

Codeforces Round #585 (Div. 2)E（状态压缩DP，思维）

最新文章

热门文章