Codeforces 1215E. Marbles
2024-10-07 03:25:26
注意到 $a$ 的值的数量并不大,考虑状压 $dp$
设 $f[S]$ 表示此时确定的数集合为 $S$ ,且按某种顺序从数列开头排列完成的最小交换次数
那么每个状态枚举最后一个填的数,加上代价后,取最小值即可
现在最大的问题是,代价怎么算...???
注意到我们每次交换相邻的两个数,这两个数和其他的数的相对位置是不变的(这个我认为是整题最关键的地方)
就是说在最优情况下,我们把数字 $x$ 统一交换到某个段时,产生的代价即为这个数原本每个位置和此时这个位置之前还没确定的数的数量....
讲得好绕啊,看代码比较好理解吧............
复杂度算一下达到了 $1e8$ 级别,但是 $CF$ 跑得快,这一题时限又长,所以很稳
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=4e5+,M=(<<)+;
int n,a[N],b[N],cnt[];
ll cst[][],f[M];
// cst[i][j] 表示把值i统一交换到值j之前的代价
int main()
{
n=read();
for(int i=;i<=n;i++) a[i]=read();
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
cst[a[i]][j]+=cnt[j];
cnt[a[i]]++;
}
int mx=(<<)-;
memset(f,0x3f,sizeof(f)); f[]=;
for(int i=;i<=mx;i++)
for(int j=;j<;j++)
{
if(!((i>>j)&)) continue;
ll t=;
for(int k=;k<;k++)
{
if((i>>k)&) continue;
t+=cst[j+][k+];//代价和为 和此时还没确定的所有数交换的代价
}
f[i]=min(f[i],f[i^(<<j)]+t);
}
printf("%lld\n",f[mx]);
return ;
}
最新文章
- Web中的XHRHttpRequest
- bzoj1150: [CTSC2007]数据备份Backup--贪心+优先队列维护堆
- 推荐10个bootstrap及其他框架的后台管理模板
- Excel公式中双引号和单引号输入和显示以及函数的选择确认
- NOIP2003 传染病防治
- R语言学习网站
- 【51NOD1847】奇怪的数学题 min_25筛
- Linux扩展分区记录
- 第28月第22天 iOS动态库
- Openssl源代码整理学习
- php下载远程图片到本地
- iOS性能优化总结
- 漫步Java------初识java
- vue-cli 创建的项目,在 nginx 上配置启用浏览器缓存
- Linux日志文件总管——logrotate
- MariaDB学习记录
- spring boot +druid数据库连接池配置
- LVS入门篇(二)之LVS基础
- onclick监听
- css3动画(animation)效果2-旋转的星球
热门文章
- SRM331-CarolsSinging(暴力,位运算)
- 如何基于String实现同步锁?
- python3笔记八:python数据类型-Number数字
- tensorflow实现LeNet-5模型
- defineProperty和defineProperties介绍
- 怎样用 Bash 编程:语法和工具
- 对保存的参数checkpoints进行可视化读取 1.pywrap_tensorflow.NewCheckpoint(获得checkpoint的读取器) 2.np.save(对npy文件进行保存) 3.tl.file.load_npy_to_any(对保存的npy文件进行读取)
- SpringBoot 启动流程
- CompletableFuture引入
- Selenium 2自动化测试实战9(简单元素操作)