链接：https://ac.nowcoder.com/acm/contest/882/F
来源：牛客网
时间限制：C/C++ 4秒，其他语言8秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Given 2N people, you need to assign each of them into either red team or white team such that each team consists of exactly N people and the total competitive value is maximized.
Total competitive value is the summation of competitive value of each pair of people in different team.
The equivalent equation is ∑2Ni=1∑2Nj=i+1(vij if i-th person is not in the same team as j-th person else 0)∑i=12N∑j=i+12N(vij if i-th person is not in the same team as j-th person else 0)
输入描述:
The first line of input contains an integers N. Following 2N lines each contains 2N space-separated integers vijvij is the j-th value of the i-th line which indicates the competitive value of person i and person j. * 1≤N≤141≤N≤14 * 0≤vij≤1090≤vij≤109 * vij=vjivij=vji
输出描述:
Output one line containing an integer representing the maximum possible total competitive value.
示例1
输入
1 0 3 3 0
输出
3
题目大意:有2*n个人,你要把他们分成两组,每组每一个人对于另一个人都有一个竞争值,竞争值总和最大是多少
题目思路:n的范围是1-14那么就可以用暴力搜索,暴力搜索可以非常简单的枚举出C(2*n,n)的情况.然后对于每一种情况计算一下他的竞争值之和取最大值就是答案
首先看一下如何进行暴力枚举:(具体注释+超时代码)
void dfs(int k,int cnt1,int cnt2)
{
if(k==2*n+1)//回溯条件
{
ll cnt=0;
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
cnt+=mp[num1[i]][num2[k]];
maxl=max(maxl,cnt);//取最大值
return;
}
if(cnt1<n)//分到一队
{
num1[cnt1+1]=k;
dfs(k+1,cnt1+1,cnt2);
}
if(cnt2<n)//分到二队
{
num2[cnt2+1]=k;
dfs(k+1,cnt1,cnt2+1);
}
} 这个代码超时了 复杂度为O(C(2n,n)*n^(2)).
看来想过题也没有那么容易,需要加一点思维了,我们可以用 两个类似指针的下标控制两个数组,如果进入2队的多了一个,那么它对总的贡献值就都加进去,比如 1 2 3 4 :
首先1为到1队,2队没有所以不用加.
2分到2队,此时1队里有1,所以sum+=mp[2][1]
3分到1队.此时2队里有2,所以sum+=mp[3][2]
4分到2队,此时1队里有1 3 所以sum+=mp[4][1] sum+=mp[4][3]
其实这样就把 [1 2] [1 4] [3 2] [3 4] 都给枚举完了 而且咱们可以在过程中处理那么总的处理就是n 复杂度:O(C(2n,n)*n)
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1000000007;
ll n,m;
ll maxl=0;
ll mp[30][30];
ll num1[30],num2[30];
ll pos1=0,pos2=0;
void dfs(int k,int cnt1,int cnt2,ll sum)
{
if(k==2*n+1)
{
maxl=max(maxl,sum);
return;
}
if(cnt1<n)
{
ll temp=0;
num1[++pos1]=k;
for(int i=1;i<=pos2;i++)
temp+=mp[k][num2[i]];
dfs(k+1,cnt1+1,cnt2,sum+temp);
pos1--;
}
if(cnt2<n)
{
ll temp=0;
num2[++pos2]=k;
for(int i=1;i<=pos1;i++)
temp+=mp[k][num1[i]];
dfs(k+1,cnt1,cnt2+1,sum+temp);
pos2--;
}
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=2*n;i++)
for(int k=1;k<=2*n;k++)
scanf("%lld",&mp[i][k]);
dfs(1,0,0,0);
printf("%lld\n",maxl);
}
其实如果这个题目数据没有那么强,也可以用随机数做,随机把数分成两组,最后符合要求的数据取平均值就是答案:
与牛客第一场的 F 思路相同:牛客第一场F 随机数结论
代码如下:(这题数据太大,以下代码是答案错误的,如果普通数据&&DFS又不太会写可以用这个蒙一下):
对于这个题而言 当 随机数量达到1e8之后 结果是80是正确的可以提交,但是就会超时,所以如果 检测随机数时,算法复杂度很小可以提升到1e7-1e8的都可以用随机数.并且随机数用来找规律
代码:(答案错误): ____只是为了应用随机数而不是AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1000000007;
ll n,m;
ll maxl=0;
ll mp[30][30];
ll num1[30],num2[30];
ll pos1=0,pos2=0;
bool vis[30];
bool judge()//判断分配是否合理
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
if(!vis[num1[i]]) vis[num1[i]]=true;
else return false;
if(!vis[num2[i]]) vis[num2[i]]=true;
else return false;
}
return true;
}
int main()
{
srand(time(0));
scanf("%lld",&n);
for(int i=1;i<=2*n;i++)
for(int k=1;k<=2*n;k++)
scanf("%lld",&mp[i][k]);
ll cnt=0,sum=0;
for(int k=1;k<=6000000;k++)
{
ll temp=0;
for(int i=1;i<=n;i++)
{
num1[i]=rand()%(2*n)+1;
for(int j=1;j<=i-1;i++)
temp+=num1[]
}
for(int i=1;i<=n;i++)
num2[i]=rand()%(2*n)+1;
if(judge())
{
cnt++;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
sum+=mp[num1[i]][num2[j]];
}
}
printf("%lld\n",sum/cnt);
return 0;
}
总结:一步一步走,慢慢来,今天一定会比昨天更优秀呀!
京公网安备 11010502036488号