[洛谷P2210]Haywire
2024-08-31 10:09:02
题目大意:有$n(n\leqslant12)$个数,每个数和其他三个数连边,求一个排列,使得边的长度最小
题解:状压$DP$,$f_{i,j}$表示当前确定的数状态为$i$,有$j$条边起点被确定终点没有确定的最短距离
卡点:无
C++ Code:
#include <cstdio>
#define maxn 13
int n, m;
int s[maxn][3];
int f[1 << maxn][maxn * 3];
inline int min(int a, int b) {return a < b ? a : b;}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d%d%d", s[i], s[i] + 1, s[i] + 2);
s[i][0]--, s[i][1]--, s[i][2]--;
}
int U = 1 << n;
__builtin_memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < U; i++) {
for (int j = 0; j < n; j++) if (!(i & 1 << j)){
for (int k = 0; k <= n * 3; k++) {
int tmp = k;
if (i & 1 << s[j][0]) tmp--;
else tmp++;
if (i & 1 << s[j][1]) tmp--;
else tmp++;
if (i & 1 << s[j][2]) tmp--;
else tmp++;
f[i | 1 << j][tmp] = min(f[i | 1 << j][tmp], f[i][k] + tmp);
}
}
}
printf("%d\n", f[U - 1][0]);
return 0;
}
最新文章
- UML(Unified Modeling Language)统一建模语言
- css中import与link用法区别
- 安卓向服务器发送List数据
- Python-requests之POST Data的json问题
- 使用CInternetSession CHttpFile下载网页链接地址的文件
- UVa 10253 (组合数 递推) Series-Parallel Networks
- 安装Hadoop系列 — eclipse plugin插件编译安装配置
- SolrCloud 5.2.1 installation and configuration
- android 显示特殊符号
- codeforces 245H . Queries for Number of Palindromes 区间dp
- 【第二篇】Volley的使用之加载图片
- [LeetCode] Is Subsequence 题解
- 用java理解程序逻辑小结
- solr中Cache综述
- Vue2 第二天学习
- golang显示本机IP代码
- maven項目創建紅叉
- oo第八次作业--5,6,7次作业总结
- HDU 3530 单调队列
- Urllib库的基本用法
热门文章
- Django---URL、Views
- 微信小程序 - 生命周期 - 参数传递
- 修改二维码生成插件jquery.qrcode.js支持加入自定义LOGO
- pywinauto 使用
- angularjs路由不断刷新当前页面
- Hadoop(19)-MapReduce框架原理-Combiner合并
- 清华大学《C++语言程序设计基础》线上课程笔记01---基础概念与一些注意事项
- POJ1679(次小生成树)
- 在WPF中自定义控件(3) CustomControl (上)
- Error loading MySQLdb module: libmysqlclient.so.18: cannot open shared object file: No such file or directory