CodeForces - 580D Kefa and Dishes 状态压缩dp
CodeForces - 580D Kefa and Dishes 状态压缩dp
题意：
小图的餐厅共有 n 道菜，他想设计一个宴会的菜单及上菜流程，包含 m 道不重复的菜。
首先，第 i 道菜的美味值为 ai，而一个宴会的基础美味值等于菜单上所有菜品的美味值之和。
其次，上菜的流程会影响最终的美味值，一共有 k 条规则。第 i 条规则对应两道菜品 xi 和 yi，如果在上菜流程中，yi 紧跟在 xi 后面，则宴会的美味值会提升 ci 点。
当然，小图想设计出美味值最高的宴会，帮他计算这一最大值并输出。
Input：
2 2 1 1 1 2 1 1 Output： 3
for(int S=0;S<(1<<n);S++){ for(int i=0;i<n;i++){ if(S&(1<<i))
那么用哪些食物呢，首先食物不能是已经吃过的了，就是前面没用过，对应代码中的这一段：
if(!(S&(1<<j)))
如果以上条件都满足了，那么我们就进行状态转移，第一种是不吃，第二种是吃，两者取最大即可。
dp[S|(1<<j)][j]=max(dp[S|(1<<j)][j],dp[S][i]+a[j]+val[i][j]);
最后，本题的独到之处在于限制只能吃m个食物。然而我们状态转移是吃n个食物的，但问题不大。由于状态压缩枚举了每个子集，我们也可以在最后的dp[S][i]中找到长度为m的S，在考虑它最后在吃
i个的最大值，得出答案.
下面是全部的代码：
#include<bits/stdc++.h>using namespace std;const int maxn = 20;const int maxm = 400;int a[maxn];int val[maxn][maxn];long long dp[1<<maxn][maxn];int cal(int x){ int ans=0; while(x){ if(x&1) ans++;
x>>=1;
} return ans;
}int main(){ int n,m,k;
cin>>n>>m>>k; for(int i=0;i<n;i++) cin>>a[i]; for(int i=1;i<=k;i++){ int b,c,d;
scanf("%d%d%d",&b,&c,&d);
val[b-1][c-1]=d;
} for(int i=0;i<n;i++) dp[1<<i][i]=a[i]; for(int S=0;S<(1<<n);S++){ for(int i=0;i<n;i++){ if(S&(1<<i)) { for(int j=0;j<n;j++) { if(!(S&(1<<j))) {
dp[S|(1<<j)][j]=max(dp[S|(1<<j)][j],dp[S][i]+a[j]+val[i][j]);
}
}
}
}
} long long ans=0;
for(int S=0;S<(1<<n);S++){ if(cal(S)==m) { for(int i=0;i<n;i++) ans=max(ans,dp[S][i]);
}
}
cout<<ans<<endl;return 0;}