indeed在线第二题

直接暴力哇

#include <bits/stdc++.h>using namespace std;int n,k,m,a,b,u,ans,val[15][15],tmp[15];int main(){ while(cin>>n>>k>>m){ ans=0; memset(val,0,sizeof(val)); for(int i=1;i<=m;i++){ cin>>a>>b>>u; val[a][b]=u; } for(int i=1;i<=n;i++)tmp[i]=i; do{ int num=0; for(int i=1;i<=k;i++){ for(int j=i+1;j<=k;j++)num+=val[tmp[i]][tmp[j]]; } for(int i=k+1;i<=2*k;i++){ for(int j=i+1;j<=2*k;j++)num+=val[tmp[i]][tmp[j]]; } ans=max(ans,num); }while(next_permutation(tmp+1,tmp+1+n)); cout<<ans<<endl; }} 【 在 willian123 (willian123) 的大作中提到: 】 : 今天有人做indeed在线测试题吗？第二题mixing谁有高效的解法？ : --

n只有8，全排列之后，计算前2*k个就可以了。

【 在 caoyu01 的大作中提到: 】 : n只有8，全排列之后，计算前2*k个就可以了。 我看了你的算法，有个问题，如果策略一共包含了6个成分，但是一个药是由4个成分组成的，那第二种药按照题意是不是构成不了？但是这个算法也会把剩余那个2个成分组成的要算到最后的结果里？

你能把题目放上来么 不然谁知道你在说嘛？

有个条件说了，k<=n/2…… 【 在 willian123 (willian123) 的大作中提到: 】 : 我看了你的算法，有个问题，如果策略一共包含了6个成分，但是一个药是由4个成分组成的，那第二种药按照题意是不是构成不了？但是这个算法也会把剩余那个2个成分组成的要算到最后的结果里？

你的意思是一个药物的成分小于等于k也行？ 【 在 caoyu01 的大作中提到: 】 : 有个条件说了，k<=n/2…… : : 【 在 willian123 (willian123) 的大作中提到: 】 : : 我看了你的算法，有个问题，如果策略一共包含了6个成分，但是一个药是由4个成 : ......... 发自「贵邮」

题目没有了 【 在 a940100079 的大作中提到: 】 : 你能把题目放上来么 : 不然谁知道你在说嘛？ : 发自「贵邮」

我的意思是，n的全排列，然后第一种药选择前k个，第二种药选择接下来的k个…看代码吧 【 在 willian123 (willian123) 的大作中提到: 】 : 你的意思是一个药物的成分小于等于k也行？