狀態壓縮dp，Codeforces ----- Kefa and Dishes [狀壓dp]

題目傳送門:580D

?

題目大意:給你n道菜以及每道菜一個權值,k個條件,即第y道菜在第x道后馬上吃有z的附加值,求從中取m道菜的最大權值

看到這道題,我們會想到去枚舉,但是很顯然這是會超時的,再一看數據范圍,n只有18,那么我們就可以用狀壓去做了,dp數組也還是比較好定義的,dp[i][state]表示現在吃到第i道菜狀態為state的最大權值,既然有k個限制條件我們就按每個菜去擴展,然后就是一個裸的狀壓dp了,記得要開long long

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#define in(i) (i=read())
using namespace std;
typedef long long lol;
lol read()
{lol ans=0,f=1;char i=getchar();while(i<'0'||i>'9'){if(i=='-') f=-1;i=getchar();}while(i>='0'&&i<='9'){ans=(ans<<1)+(ans<<3)+i-'0';i=getchar();}return ans*f;
}
lol dp[19][1<<18];
lol a[19],b[19][19];
lol n,m,k;
int main()
{lol ans=0;in(n);in(m);in(k);for(lol i=1;i<=n;i++) in(a[i]);for(lol i=1;i<=k;i++){lol u,v,c;in(u);in(v);in(c);b[u][v]=c;}for(lol i=1;i<=n;i++) dp[i][1<<i-1]=a[i];for(lol i=0;i<(1<<n);i++){lol cnt=0;for(lol j=1;j<=n;j++){if(i&(1<<(j-1))){cnt++;//這里的cnt是已經經過前面的if的語句,也就是說這里的cnt是看此狀態有多少位是1,也就是會吃多少道菜,所以才有了下面的if(cnt==m)這個語句for(lol k=1;k<=n;k++){if(!(i&(1<<k-1))){dp[k][i|(1<<k-1)]=max(dp[k][i|(1<<k-1)],dp[j][i]+a[k]+b[j][k]);}}}}if(cnt==m){for(lol j=1;j<=n;j++)if(i&(1<<(j-1)))//一定要記得判斷ans=max(ans,dp[j][i]);}}cout<<ans<<endl;return 0;
}