有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