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;
}