http://codeforces.com/contest/580/problem/D
题意:
有个人去餐厅吃饭,现在有n个菜,但是他只需要m个菜,每个菜只吃一份,每份菜都有一个欢乐值。除此之外,还有一些规则,x,y,w代表的是如果x吃完后吃y,那么还能获得额外的w欢乐值。计算所能获得的最大欢乐值。
思路:
看到别人说要用状压dp来做,我才恍然大悟啊,感觉自己对于状压dp实在是太不敏感了。
d【i】【j】表示在当前i状态时最后一份吃的是j的最大欢乐值。
状态转移什么的请看代码吧。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 20+5; 17 18 ll n, m, t; 19 ll val[maxn]; 20 ll d[1<<18][maxn], r[maxn][maxn]; 21 22 int main() 23 { 24 //freopen("in.txt","r",stdin); 25 while(~scanf("%lld%lld%lld",&n,&m,&t)) 26 { 27 for(int i=0;i<n;i++) scanf("%lld",&val[i]); 28 29 memset(r,0,sizeof(r)); 30 for(int i=0;i<t;i++) 31 { 32 int x,y; ll w; 33 scanf("%d%d%lld",&x,&y,&w); 34 x--; y--; 35 r[x][y]=w; 36 } 37 38 memset(d,-1,sizeof(d)); 39 for(ll i=0;i< n;i++) 40 { 41 d[1<<i][i]=val[i]; 42 } 43 44 ll ans=0; 45 46 for(ll i=0;i<(1<<n);i++) 47 { 48 int cnt=0; 49 ll tmp=i; 50 while(tmp) //计算出i状态已经吃了几份菜了 51 { 52 if(tmp&1) cnt++; 53 tmp>>=1; 54 } 55 56 for(ll j=0;j<n;j++) 57 { 58 if(cnt==m && (i&(1<<j))) ans=max(ans,d[i][j]); //如果已经吃了m份菜,分别求最后吃的是j的时候的欢乐值,维护最大值 59 if(cnt==m || !(i&(1<<j))) continue; 60 61 //如果还没够m份,接下计算吃k时所能获得的最大欢乐值 62 for(ll k=0;k<n;k++) 63 { 64 if(i&(1<<k)) continue; 65 d[(1<<k)|i][k]=max(d[(1<<k)|i][k],d[i][j]+val[k]+r[j][k]); 66 } 67 } 68 } 69 printf("%lld ", ans); 70 } 71 return 0; 72 }