首页 > 其他分享 >CF580D Kefa and Dishes

CF580D Kefa and Dishes

时间:2023-02-25 19:11:51浏览次数:37  
标签:CF580D 20 Dishes int num Kefa cost

有n个菜(0<n<=18)第i个菜的满意度为a[i ](0<=ai<=10^9),有k个规则,如果在吃完第xi个菜之后吃了第yi个菜,

会额外获得ci的满意度。kefa要吃m道任意的菜(0<m<=n),但是他希望自己吃菜的顺序得到的满意度最大

 

  f[j][i] = f[j^(1<<i) ] [k ]+ a[i] +VALUE(k,i)

 

#include <iostream>
#include <cstring>
using namespace std;
 const int M =5e5+30;
 
 #define int long long
 int f[M][20],cost[20][20],n,m,K;
  int a[20];
  
  
  int count(int x){
    int num = 0;
    while(x) num += (x & 1), x >>= 1; 
    return num;
}
 main(){
 	int i,j,k;
 	cin>>n>>m>>K;
 	for(i=0;i<n;i++) cin>>a[i];
 	for(i=1;i<=K;i++){
 		int x,y;
 		cin>>x>>y;
 		cin>>cost[x-1][y-1];
 	}

	int ans=0;
 	for(j=0;j<(1<<n);j++)
 	  for(i=0;i<n;i++){
 	  	int flag=0;
 	  	
 	  	if(j&(1<<i)){
 	  		for(k=0;k<n;k++){
 	  			if(i!=k&&(j&(1<<k))){
	 	  		 	flag=1;
		 	  		f[j][i]=max(f[j][i],f[j^(1<<i)][k]+
		 	  		cost[k][i]+a[i]);
 	  		 	}
 	  		}
 	  	  if(flag==0) f[j][i]=a[i];
 	  	}
 	  	 if(count(j)==m) ans=max(ans,f[j][i]);
 	  }
 	
 	   cout<<ans<<endl;
 	 
 } 
 

 

标签:CF580D,20,Dishes,int,num,Kefa,cost
From: https://www.cnblogs.com/towboa/p/17155102.html

相关文章

  • codeforces 580C Kefa and Park (树上DFS)
    Description:Kefadecidedtocelebratehisfirstbigsalarybygoingtotherestaurant.Helivesbyanunusualpark.Theparkisarootedtreeconsistingof n ve......
  • CF580E - Kefa and Watch 线段树维护哈希
    题目思路区间修改+区间查询,考虑用线段树维护哈希实现。那么首先,需要明确判断循环节的方式:如上图所示是一个重要的结论:当区间的哈希值与的哈希值相等时,那么该区间是以为循环......
  • Codeforces Round #321 (Div. 2) C. Kefa and Park(树+dfs)
    https://codeforces.com/contest/580/problem/C题目大意:给定一棵树,这棵树总共有n个节点,自己家住在节点1(根节点);每个节点都有一个标记a[i],标记为1就是这个地方有猫,0就表......