19牛客多校2-F(DFS,权值计算散步于过程中以优化时间)
Partition problem
https://ac.nowcoder.com/acm/contest/882/F
输出描述:
Output one line containing an integer representing the answer.
示例1
输入
1 0 3 3 0
输出
3
题意：
给定2n个人，每两个人间存在一个竞争值 分析：
自然想到要枚举子集，倘若单纯地考虑每一元素 放/不放 在组1中，并在 组1/组2 放满后进行统计&更新最优值，则复杂度O(C(2N,N)*N^2)，显然会T。
考虑设置两个集合(数组)，分别存放已分配进组1的人和已分配进组2的人，则dfs遍历到某一个人时，两种选择——放入组1/组2，每一个选择下此人所贡献的权值即为他与相对组的已分配集合中所有人的竞争值得和，这样对于每一个二元对(i,j)，二元对产生的权总会在 二元对中较晚被遍历到的人被遍历时 所统计。同时，权值的和的计算分解在dfs的过程中而不是在最后到达叶边界时统计可以减去重复的计算(即搜索树以根开始的某一段前缀 在其对应到不同叶节点时，这段前缀不会被重复计算)，这样应该可以显著优化搜索带来的常数，貌似复杂度可达 O(C(2N,N)*N)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c[30][30];
ll ans;
vector<int> a,b;
void dfs(int u,int num,ll s){
int i,j;
ll sum=s;
if(num==n){
for(i=u;i<=2*n;i++){//组1已满，剩余的人分入组2并统一计算权值
for(j=0;j<a.size();j++)
s+=c[i][a[j]];
}
ans=max(ans,s);
return ;
}
else if(u-1-num==n){
for(i=u;i<=2*n;i++){//组2已满，剩余的人分入组1并统一计算权值
for(j=0;j<b.size();j++)
s+=c[i][b[j]];
}
ans=max(ans,s);//更新最优值
return ;
}
// join in Group1
sum=s; a.push_back(u);
for(i=0;i<b.size();i++)//计算贡献
sum+=c[u][b[i]];
dfs(u+1,num+1,sum); a.pop_back();
// join in Group2
sum=s; b.push_back(u);
for(i=0;i<a.size();i++)//计算贡献
sum+=c[u][a[i]];
dfs(u+1,num,sum); b.pop_back();
}
int main(){
int t,i,j,k;
cin>>n;
for(i=1;i<=2*n;i++){
for(j=1;j<=2*n;j++)
scanf("%d",&c[i][j]);
}
dfs(1,0,0);
cout<<ans;
return 0;
}
