P2196 挖地雷

题目链接：https://www.luogu.com.cn/problem/P2196

思路

没错，我又再重学dp。又开始做水题了。
这个题数据量很小，可以直接把图进行遍历。每次开始的点分别是1～N。
dp[v] = max(dp[v],dp[u] + w[v])

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e3+10;
using namespace std;

int N,ans,cur,Ed;
int w[maxn],dp[maxn],from[maxn];
vector<int> order;
int h[maxn],e[maxn],ne[maxn],idx;
void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}

void dfs(int u){
    if(dp[u] > cur) cur = dp[u],Ed = u;
    for(int i = h[u];i;i = ne[i]){
        int v = e[i];
        if(dp[u] + w[v] > dp[v]){
            dp[v] = dp[u] + w[v];
            from[v] = u;
        }
        dfs(v);
    }
}

void save_ans(){
    if(cur > ans){
        order.clear();
        ans = cur;
        while(from[Ed]){
            order.push_back(Ed);
            Ed = from[Ed];
        }
        order.push_back(Ed);
    }
}

int main(){
    // debug;
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++) cin>>w[i];
    for(int i = 1;i<=N-1;i++){
        for(int j = i+1;j<=N;j++){
            int t;cin>>t;
            if(t) add(i,j);
        }
    }
    for(int i = 1;i<=N;i++) {
        memset(dp,0,4*N+10);
        memset(from,0,4*N+10);
        cur = 0;
        dp[i] = w[i];
        dfs(i);
        save_ans();
    }
    for(int i = order.size()-1;i>=0;i--) cout<<order[i]<<" ";
    cout<<'\n';
    cout<<ans<<'\n';

    return 0;
}