题解

4. 挖地雷

状态定义

设 dp[i] 表示从地窖 i 出发（包括 i）能挖到的最大地雷数。

合理性：由于路径只能从编号小到大，且不能回头，从 i 出发的最优解只取决于它能到达的后续地窖。这是一个典型的 DAG 上的最长路问题，可以用动态规划从后向前计算。
转移方程
且

推导：从 i 出发，你可以选择直接结束（只拿 mine[i]），也可以选择走到某个相邻的 j（j > i），然后从 j 继续走。走到 j 后能获得的最大地雷数就是 dp[j]，加上 mine[i] 即为总地雷数。取所有合法 j 的最大值。若没有可走的 j，则 dp[i] = mine[i]。

计算顺序
由于 i 只依赖于更大的 j，所以从 n 到 1 逆序计算。

最终答案
max(dp[1..n]) 即为全局最大地雷数。

#include<bits/stdc++.h>
using namespace std;
int n;
int mine[27];
int g[27][27];
int main(){
    cin>>n;
    vector<int>dp(n+1);
    for(int i=1;i<=n;i++)cin>>mine[i];
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>g[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        dp[i]=mine[i];
        for(int j=i+1;j<=n;j++){
            if(g[i][j]==1)dp[i]=max(mine[i]+dp[j],dp[i]); 
        }
    }
    int ans=dp[1];
    for(int i=2;i<=n;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}