Luogu3694 邦邦的大合唱站队（状压DP）

拼搏现实的明天。 2021-11-17 05:10 215阅读 0赞

状态由\\(从前往后排好的长度\\)和\\(排好的团队\\)决定，\\(DP\\)方程挺有思考价值的。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define R(a,b,c) for(register int a = (b); a <= (c); ++ a) #define nR(a,b,c) for(register int a = (b); a >= (c); -- a) #define Max(a,b) ((a) > (b) ? (a) : (b)) #define Min(a,b) ((a) < (b) ? (a) : (b)) #define Fill(a,b) memset(a, b, sizeof(a)) #define Abs(a) ((a) < 0 ? -(a) : (a)) #define Swap(a,b) a^=b^=a^=b #define ll long long //#define ON_DEBUG #ifdef ON_DEBUG #define D_e_Line printf("\n\n----------\n\n") #define D_e(x) cout << #x << " = " << x << endl #define Pause() system("pause") #define FileOpen() freopen("in.txt","r",stdin); #else #define D_e_Line ; #define D_e(x) ; #define Pause() ; #define FileOpen() ; #endif struct ios{ template<typename ATP>ios& operator >> (ATP &x){ x = 0; int f = 1; char c; for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar(); x*= f; return *this; } }io; using namespace std; int num[21], sum[100007][21]; int bin[21]; int f[(1 << 20) + 7]; int main(){ int n, m; io >> n >> m; R(i,1,n){ int x; io >> x; R(j,1,m) sum[i][j] = sum[i - 1][j]; ++num[x]; ++sum[i][x]; } bin[1] = 1; R(i,2,m) bin[i] = bin[i - 1] << 1; Fill(f, 0x3f3f3f3f); f[0] = 0; int maxx = (1 << m) - 1; R(i,0,maxx){ int len = 0; R(j,1,m){ if(i & bin[j]){ len += num[j]; } } R(j,1,m){ if(i & bin[j]){ f[i] = Min(f[i], f[i ^ bin[j]] + num[j] - (sum[len][j] - sum[len - num[j]][j])); } } } printf("%d", f[maxx]); return 0; }

![1570282-20190721172128773-188577820.png][]

转载于:https://www.cnblogs.com/bingoyes/p/11221869.html

[1570282-20190721172128773-188577820.png]: /images/20211116/0ac90763fb3d40729cd4b403a84847b3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】Most Powerful

[E-Most Powerful\_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)][E-Most Powerful_dp_ _nowcoder.com]

以你之姓@/ 2024年03月17日 08:58/ 0 赞/ 72 阅读

相关【状压DP】简单环

怎么办，感觉现在所谓会的算法都是云的以为自己会，然后随便出一道题就不会云玩家是吧好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好

柔情只为你懂/ 2024年03月17日 08:57/ 0 赞/ 59 阅读

相关【题解】Luogu P2831 愤怒的小鸟状压dp

状压dp -------------------- 思路来自[@real\_l][real_l] 由于抛物线$y=a\\{x^2\}+b\y$只有两个参数，初中数学老

桃扇骨/ 2023年08月17日 16:49/ 0 赞/ 163 阅读

相关 group 状压dp

　　应某些人要求，我把标签删掉了　　这是一道好题。　　一看$c<=16$果断状压，但是怎么压？　　一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c

逃离我推掉我的手/ 2023年08月17日 16:48/ 0 赞/ 138 阅读

相关 HDU3182-状压dp

Hamburger Magi Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

川长思鸟来/ 2022年07月13日 14:56/ 0 赞/ 223 阅读

相关 HDU4114-floyd+ 状压dp

Disney's FastPass Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/327

柔光的暖阳◎/ 2022年07月11日 13:40/ 0 赞/ 232 阅读

相关状压dp（瞎BB）

最近在写状压dp，写得不太顺利啊，抠很久才抠出来。可见如此之菜。状态压缩dp（简称状压dp）是一种非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数

迷南。/ 2022年06月17日 08:13/ 0 赞/ 242 阅读

相关中国互联网：“城邦”时代

21世纪接下来的第二个十年，城邦竞争力──或者说是平台型企业的能力，将成为重新界定中国互联网各大公司疆域与座次的关键因素。在21世纪即将开始第二个10年的节点上，中国互联网

电玩女神/ 2022年05月15日 03:34/ 0 赞/ 381 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 310 阅读

相关 Luogu3694 邦邦的大合唱站队（状压DP）

状态由\\(从前往后排好的长度\\)和\\(排好的团队\\)决定，\\(DP\\)方程挺有思考价值的。 include <iostream> include <cst

拼搏现实的明天。/ 2021年11月17日 05:10/ 0 赞/ 216 阅读