Acwing 5729.闯关游戏 状压DP

Acwing 5729.闯关游戏 状压DP

题目链接

题意：

现在进行一个闯关游戏，一共有 \(n\) 个关卡，第 \(i\) 个关卡的分数为 \(w_i\)。另外还有 \(k\) 个联动彩蛋。如果玩家通过第 \(x\) 个关卡后，紧接着通过了第 \(y\) 个关卡，就可以获得额外 \(c\) 分。现在你需要恰好通过 \(m\) 个不同关卡，顺序自由安排。使得总得分最大。

\(1\le m \le n \le 18\).

思路：

注意到数据范围，贪心不可行。不妨尝试状压DP。

数组第一维自然就是表示选择的状态，第二维我们要考虑如何进行划分。我们可以考虑以最后一次选择的关卡进行划分。

因此，定义 \(f_{i,j}\) 表示状态为 \(i\) 时且最后一次选择通过 \(j\) 关卡时，所能获得的最大分数。

接着考虑如何转移。结合题意中的联动彩蛋，很自然的想到，我们可以去枚举倒数第二次的关卡选择，这样便可以进行状态转移。

即 \(f_{i,j}=max(f_{i,j},f_{i-(1<<j),k}+g_{k,j}+w_j)\)。

最后我们只需要再枚举一遍，找出状态中恰好选取了 \(m\) 个关卡的状态，更新答案即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 20, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

LL f[1<<N][N];
int w[N],g[N][N];
void Showball(){
   int n,m,k;
   cin>>n>>m>>k;
   for(int i=0;i<n;i++) cin>>w[i];
   while(k--){
      int x,y,c;
      cin>>x>>y>>c;
      g[x-1][y-1]=c;
   }

   for(int i=0;i<n;i++) f[1<<i][i]=w[i];

   for(int i=0;i<1<<n;i++){
      for(int j=0;j<n;j++){
         if(i>>j&1){
            for(int k=0;k<n;k++){
               if(k!=j&&i>>k&1){
                  f[i][j]=max(f[i][j],f[i-(1<<j)][k]+g[k][j]+w[j]);
               }
            }
         }
      }
   }

   LL ans=0;
   for(int i=0;i<1<<n;i++){
      int cnt=0;
      for(int j=0;j<n;j++){
         if(i>>j&1) cnt++;
      }
      if(cnt==m){
         for(int j=0;j<n;j++){
            ans=max(ans,f[i][j]);
         }
      }
   }
   cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}