信息学奥赛一本通TT1262-挖地雷 差点睡不着觉 服了

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
struct f{
    int xi,yi;
}t[20005];
bool mp[205][205];
int n,a[205],b[205],dp[205];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=a[i];
    }
    for(int i=1;;i++){
        cin>>t[i].xi>>t[i].yi;
        if(t[i].yi==0){
            break;
        }
        mp[t[i].xi][t[i].yi]=true;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            if(mp[j][i]&&dp[j]+a[i]>dp[i]){
                dp[i]=dp[j]+a[i];
                b[i]=j;
            }
        }
    }
    int hh=dp[1],kk=1;
    for(int i=1;i<=n;i++){
        if(dp[i]>hh){
            hh=dp[i];
            kk=i;
        }
    }
    int r;
    while(b[kk]){
        r=b[kk];
        b[kk]=-1;
        kk=r;
    }
    cout<<kk;
    while(++kk<=n){
        if(b[kk]==-1){
            cout<<"-"<<kk;
        }
    }
    cout<<endl<<hh;
    return 0;
}