Atcoder dp_u Grouping 状压dp_u - grouping-程序员宅基地

技术标签: 状压  dp  状压dp  

文章目录


题目链接

题意

n n n只兔子分组,每两只兔子之间有一个亲密度,当然亲密度也有可能是负数,表示这两只兔子有仇.
一个组的亲密度是这一组里所有兔子两两的亲密度之和,问合理分组下最大的总亲密度.
n ≤ 16 n\leq16 n16.

题解

状压 d p dp dp,枚举集合, d p S dp_S dpS表示集合 S S S表示的兔子们合理分组的最大总亲密度.
则从小到大枚举集合,假设 S S S的兔子全部被分在一组里,得到 S S S的初始值.
然后枚举 S S S的真子集 i i i,用 d p S ⊕ i + d p i dp_{S \oplus i}+dp_i dpSi+dpi更新 d p S dp_S dpS.状态很明确,正确性很显然.
时间复杂度为 O ( 3 n + n 2 × 2 n ) O(3^n+n^2\times2^n) O(3n+n2×2n).

#include<bits/stdc++.h> //Ithea Myse Valgulious
const int yuzu=1<<20,mod=1e9+7;
typedef ll fuko[yuzu|10];
int a[20][20];
fuko dp;
int main() {
    
 int i,n=read(),j,k;
 for (i=0;i<n;++i)
   for (j=0;j<n;++j) read(a[i][j]); 
 for (i=0;i<(1<<n);++i) {
    
   for (j=0;j<n;++j) 
     for (k=j+1;k<n;++k)
       if (i>>j&i>>k&1) dp[i]+=a[j][k];
   for (j=i&i-1;j;j=i&j-1)
     dp[i]=max(dp[i],dp[j]+dp[j^i]);
 }
 printf("%lld\n",dp[(1<<n)-1]);
}

谢谢大家.

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_31908675/article/details/119381551

智能推荐

匈牙利算法:二分图最大匹配_二分图最大匹配om√n-程序员宅基地

文章浏览阅读65次。#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510, M = 100010;int n1, n2, m;int h[N], e[M], ne[M], idx;int match[N];bool st[N];void add(int a, int b){ e[idx] = b, ne[idx] = h[_二分图最大匹配om√n

泛型_泛型 类-程序员宅基地

文章浏览阅读4.8k次。注解基础_泛型 类

二叉搜索树BST总结_bst 中序可以得到什么结果-程序员宅基地

文章浏览阅读254次。文章目录1. 概念2. 基本操作2.1 查找2.2 插入2.3 删除3. 性能分析1. 概念二叉搜索树又称二叉排序树,一颗BST应该满足以下特点:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值;若它的右子树不为空,则右子树上所有节点的值都大于根节点的值;上图就是一颗二叉搜索树,对它进行中序遍历后得到的结果是[1,2,3,4,5,6,7,8,9],我们不难发现它是一个递增的序列,注意这是二叉搜索树的一个重要性质:BST中序遍历的结果呈增序排列。在很多涉及BST的问题中都要先考_bst 中序可以得到什么结果

Flutter 路由管理 Route、Navigator 使用示例_flutter modalroute.withname('/')-程序员宅基地

文章浏览阅读1.6k次。文章目录路由管理页面跳转示例页面不传参跳转页面传参跳转Navigator 的其他跳转方式无 context 页面跳转命名路由页面跳转传参页面返回传参命名路由封装404 页面处理返回按钮拦截路由管理在 Flutter 中,页面之间的跳转是通过 Route 和 Navigator 来管理。Router是页面的抽象,类似于Android中的Activity页面。该类定义了Navigator上的抽..._flutter modalroute.withname('/')

“元宇宙”火了,这玩意到底是啥?_单机元宇宙-程序员宅基地

文章浏览阅读282次。朋友,你听说过“元宇宙”吗?2021年,一个新奇的概念名词在网络上迅速蹿红,引发科技界和投资界的广泛关注。这个概念名词,就是“元宇宙”。今天这篇文章,就给大家介绍一下它。_单机元宇宙

爱尔兰B公式和爱尔兰C公式的计算_爱尔兰公式-程序员宅基地

文章浏览阅读1.3w次,点赞10次,收藏52次。1.话务量定义话务量指在一特定时间内呼叫次数与每次呼叫平均占用时间的乘积。话务量反映了电话负荷的大小,与呼叫强度和呼叫保持时间有关。呼叫强度是单位时间内发生的呼叫次数,呼叫保持时间也就是占用时间。话务量计算方法话务量公式为:A=C * t。 A是话务量,单位为erl(爱尔兰); C是呼叫次数,单位是次/小时; t是每次呼叫平均占用时长,单位是小时/次。..._爱尔兰公式

随便推点

ffmpeg源码简析(七)解码-avformat_open_input,avformat_find_stream_info()_avformat_open_input avformat_find_stream_info-程序员宅基地

文章浏览阅读2.5k次,点赞2次,收藏4次。1.avformat_open_input打开媒体的的过程开始于avformat_open_input,因此该函数的重要性不可忽视。在该函数中,FFMPEG完成了:输入输出结构体AVIOContext的初始化;输入数据的协议(例如RTMP,或者file)的识别(通过一套评分机制):1判断文件名的后缀 2读取文件头的数据进行比对;使用获得最高分的文件协议对应的URLProtocol,通过函数指针的方式_avformat_open_input avformat_find_stream_info

python批量读取图片gps位置_基于Python就可获取照片的GPS位置信息?是的你没听错...-程序员宅基地

文章浏览阅读341次。这篇文章主要介绍了基于Python获取照片的GPS位置信息,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下。这篇文章主要介绍了基于Python获取照片的GPS位置信息,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下。说明:一般手机拍照时默认会打开地理位置开关经过压缩后,通常会将GPS信息压缩掉EXI..._python 批量 jpg gps

webpack中将打包后的文件复制到指定路径_copyplugin-程序员宅基地

文章浏览阅读4.5k次。项目中有一部分使用了另一项目的打包文件,.每次打包后都需要手动复制此文件到现有项目中,讨厌得很,故查阅后const path = require("path");const CopyPlugin = require('copy-webpack-plugin');const entryArr = []module.exports = {mode: "developmen..._copyplugin

10种软件滤波算法及其代码实现(C语言)-程序员宅基地

文章浏览阅读1w次,点赞23次,收藏210次。文章目录前言一、滤波方式介绍二、10种经典的软件滤波方法1. 限幅滤波法2. 中位值滤波法3. 算术平均滤波法4. 递推平均滤波法5. 中位值平均滤波法6. 限幅平均滤波法7. 一阶滞后滤波法8. 加权递推平均滤波法9. 消抖滤波法10. 限幅消抖滤波法参考前言本文介绍了10种常用的软件滤波方法,包含具体的滤波实现过程及优缺点,并附上了相应的代码示例(C语言)。所述滤波方法各有优劣,需根据实际应用需求进行选择。注:本文假定从8位AD中读取数据(若采用更高位的AD可定义数据类型为int);子程序为g_软件滤波

Java以form表单形式提交(文件流和json数据)_java 后端 提交form表单集合-程序员宅基地

文章浏览阅读2.8k次。目录HttpClientFormImpl层HttpClientFormimport com.alibaba.fastjson.JSONObject;import org.apache.http.Consts;import org.apache.http.HttpEntity;import org.apache.http.HttpStatus;import org.apache.http.client.ClientProtocolException;import org.apache.http._java 后端 提交form表单集合

今日头条、抖音推荐算法原理全文详解!-程序员宅基地

文章浏览阅读977次,点赞2次,收藏6次。本次分享将主要介绍今日头条推荐系统概览以及内容分析、用户标签、评估分析,内容安全等原理。一、系统概览推荐系统,如果用形式化的方式去描述实际上是拟合一个用户对内容满意度的函..._头条抖音根据哪些方面做大数据推送

推荐文章

热门文章

相关标签