AtCoder Educational DP Contest 总结
2022/8/8 23:23:06
本文主要是介绍AtCoder Educational DP Contest 总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
U Grouping
题目链接
题意:给你 \(n\) 个物品需要分组,你可以将它们分成一些组合,每组内部每一对 \((i,j)\) 都会产生一个贡献 \(a_{i,j}\)(可能为负数),问你最大可能产生的总贡献。
数据范围:\(n\leq 16\)
裸状压 DP,没啥技术含量,差评。
一看这个数据范围就知道肯定是状压 DP。
然后你知道这个以后就容易设计出 DP 状态:设 \(f(i)\) 表示选择状态为 \(i\) 时的最大总贡献。
考虑转移,转移就是你一个 \(i\) 有两种选择:
-
不划分(直接成为一个集合,即 \(i\) 内部两两直接产生贡献)
-
划分成多个集合(划分后每个集合分别计算)
但你考虑这个情况并不需要真的划分成多个集合,只要划分成 2 个然后这 2 个在递归继续划分。
划分成 2 个的过程可以通过用二进制枚举子集来实现。
总时间复杂度 \(O(2^N)\)。
代码:
#include <bits/stdc++.h> #define sz(x) (int)(x.size()) using namespace std; const int mod=1e9+7,Base=233,INF=0x3f3f3f3f; template<typename T>inline void chmax(T &a, T b){a=max(a,b);} template<typename T>inline void chmin(T &a, T b){a=min(a,b);} inline void trans(int &a,int b){a+=b;if(a>mod)a-=mod;} int n; long long a[20][20],dp[1<<16]; long long dfs(int mask) { if(dp[mask]!=-1) return dp[mask]; long long &ret=dp[mask]; ret=0; for(int i=0;i<n;i++) if((mask>>i)&1) for(int j=i+1;j<n;j++) if((mask>>j)&1) ret+=a[i][j]; for(int i=mask&(mask-1);i>0;i=(i-1)&mask) chmax(ret,dfs(i)+dfs(mask^i)); return ret; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; memset(dp,-1,sizeof(dp)); cout<<dfs((1<<n)-1)<<"\n"; return 0; }
这篇关于AtCoder Educational DP Contest 总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享