NowCoder110E Pocky游戏 状压DP
2024-10-15 04:04:50
题意:给出$N$个数和一个长为$M$、所有数在$[1,N]$范围之内的正整数序列$a_i$,求出这$N$个数的一种排列$p_1...p_N$使得$\sum\limits_{i=2}^M |p_{a_i}-p_{a_{i-1}}|$最小。$N \leq 20,M \leq 1000$
$N \leq 20$给了我们很明显的状压DP的信息,但是DP方程的思维难度还是有点大。
我们考虑按照数字从小到大地指定它在$p_i$中的位置。这样我们可以通过预处理某一个位置在$a_i$中相邻位置的数字的情况得到这一个数的贡献(也就是可以直接把绝对值符号拆开来计算它的贡献),这样子转移就会方便很多了。
设$f_i$表示已经指定了数字的序列$p$中的元素集合为$i$(eg.$i=10101$就表示指定了$p_1,p_3,p_5$,而$i=01011$表示指定了$p_1,p_2,p_4$),且对应的数为$N$个数中最小的若干个时,最小的难度值为多少。我们可以预处理$g_{i,j}$表示在序列$a$中与$i$相邻的且在集合$j$中的数的出现次数的总和(eg.如果有某一对相邻的数对为$2,3$,那么$g_{2,2^3}++,g_{3,2^2}++$),这样我们转移的时候只需要取$g_{k,i}-g_{k,2^N - 1 \, xor \, i}$就可以得到这一个数的贡献(也就是拆了绝对值之后的系数)。然后枚举转移点转移即可。
看到绝对值就要考虑一下从小到大然后拆掉绝对值符号算贡献呢qwq
#include<bits/stdc++.h> using namespace std; ] , dp[ << ] , cnt[][ << ] , cnt1[ << ] , N , M; inline int lowbit(int x){ return x & -x; } int main(){ cin >> N >> M; ; i < N ; i++) cin >> now[i]; ; while(M--){ int x; cin >> x; x--; ){ cnt[last][ << x]++; cnt[x][ << last]++; } last = x; } memset(dp , 0x3f , sizeof(dp)); dp[] = ; sort(now , now + N); ; i < << N ; i++) ; j < N ; j++) cnt[j][i] = cnt[j][i - lowbit(i)] + cnt[j][lowbit(i)]; ; i < << N ; i++){ cnt1[i] = cnt1[i - lowbit(i)] + ; ; j < N ; j++) << j)) dp[i] = min(dp[i] , dp[i ^ ( << j)] + (cnt[j][i] - cnt[j][( << N) - - i]) * now[cnt1[i] - ]); } cout << dp[( << N) - ]; ; }
最新文章
- Node.js:进程、子进程与cluster多核处理模块
- vs配置boost库
- zk FileUpload(文件上传)
- VirtualBox的四种网络连接方式
- matlab 自动阈值白平衡算法 程序可编译实现
- Non-Programmer&#39;s Tutorial for Python 3/File IO
- Android开发-API指南-任务和回退栈
- Spring Mvc和Mybatis的多数据库访问配置过程
- 练习2 J题 - 多项式求和
- Java并发编程:进程和线程的由来(转)
- 禅道SQA
- day21 python之模块和包
- 转载:python生成以及打开json、csv和txt文件
- Android典型界面设计(7) ——DrawerLayout+Fragement+ViewPager+PagerTabStrip实现双导航
- StringBuild类
- R语言2版本3版本安装
- 【three.js练习程序】旋转物体自身
- hash专题学习笔记QAQ
- (转)x264代码详细阅读之x264.c,common.c,encoder.c
- Unity资源管理机制
热门文章
- 洗礼灵魂,修炼python(33)--面向对象编程(3)—特殊类方法__init__,公有属性,私有属性
- woff字体MIME类型配置
- IDEA 编译 Jmeter 5.0(二次开发)
- Linux自制编译内核
- Spring boot + mybatis + orcale
- java基础面试题(Servlet生命周期)
- SALALchemy Session与scoped_session的源码分析
- Looper loop
- eureka分区的深入讲解
- OCX ACTIVEX程序打包个人精典案例(OCX)