购物网站 建站服务,给平面设计素材网站做素材挣钱吗,python node 网站开发,企业信息查询免费软件传送门
题意#xff1a;
给你nnn个物品#xff0c;让你将其分成任意组#xff0c;在同一个组内的i,ji,ji,j会获得ai,ja_{i,j}ai,j的收益#xff0c;让你选择一种分组方案使得收益最大。 1≤n≤16,∣ai,j∣≤1e91\le n\le 16,|a_{i,j}|\le 1e91≤n≤16,∣ai,j∣≤1e9 …传送门
题意
给你nnn个物品让你将其分成任意组在同一个组内的i,ji,ji,j会获得ai,ja_{i,j}ai,j的收益让你选择一种分组方案使得收益最大。
1≤n≤16,∣ai,j∣≤1e91\le n\le 16,|a_{i,j}|\le 1e91≤n≤16,∣ai,j∣≤1e9
思路
考虑到nnn很小所以考虑状压dpdpdp设dp[i]dp[i]dp[i]代表选的数状态为iii的时候的最大收益那么下面的问题就是如何合并转移了。。
我们利用像区间dpdpdp一样的思路枚举断点这里是枚举当前状态statestatestate的子集设枚举的子集是iii那么state−istate-istate−i就是另一个子集我们只要保证算statestatestate的时候其子集的最优解已经被求出来即可转移就是f[state]max(f[state],f[i]f[state−i])f[state]max(f[state],f[i]f[state-i])f[state]max(f[state],f[i]f[state−i])。
复杂度O(n22n3n)O(n^22^n3^n)O(n22n3n)因为枚举子集的总复杂度是3n3^n3n。
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N20,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n;
int a[N][N];
LL dp[1N],val[1N];void solve() {cinn;for(int i0;in;i) {for(int j0;jn;j) {cina[i][j];}}for(int state1;state1n;state) {for(int i0;in;i) {for(int ji1;jn;j) if((statei1)(statej1)) {val[state]a[i][j];}}}for(int state1;state1n;state) {dp[state]val[state];for(int jstate(state-1);j;j(j-1)state) {dp[state]max(dp[state],dp[state^j]dp[j]);}}coutdp[(1n)-1]endl;
}int main() {int _1;while(_--) {solve();}}
