线性dp

• 首先说下弱弱的我上来来个了拓扑排序，写完发现是有序的，哎我真的是…

状态表示：f[i]:挖到第i个点时挖到雷的最大值
状态转移：f[i]=max(f[j]+a[i]); (j到i 有通路并且j在i前面)

算法分析

1. 从前往后依次dp出能挖最多雷的路径，更新路径用pre数组表示前驱节点
2. 对于每一个i，找到f[i]的最大值即为最终的终点i

正常代码：

#include <iostream>

using namespace std;

const int N=210;

bool g[N][N];
int pre[N];
int f[N],a[N],n;

void output(int u)
{
    if(pre[u]==0) cout<<u;
    else
    {
        output(pre[u]);
        cout<<'-'<<u;
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int b,c;
    while(cin>>b>>c,b!=0) g[b][c]=true;

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

    output(k);
    cout<<'\n'<<f[k]<<endl;

    return 0;
}

多此一举的拓扑排序代码

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N=210,M=100010;

int a[N],d[N]; //雷和入度序列
int pre[N];
int e[M],ne[M],idx,h[N];
bool g[N][N];
int res[N],cnt; //拓扑排序序列
int f[N],n;//dp数组

void topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(d[i]==0) q.push(i);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        res[cnt++]=u;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0) q.push(j);
        }
    }
}

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void output(int x)
{
    if(x==pre[x]) cout<<x;
    else 
    {
        output(pre[x]);
        cout<<'-'<<x;
    }
}

int main()
{
    memset(h,-1,sizeof f);
    for(int i=0;i<N;i++) pre[i]=i;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    int a1,a2;
    while(cin>>a1>>a2,a1!=0)
    {
        add(a1,a2);
        g[a1][a2]=1;
        d[a2]++;
    }

    topsort();

    int k=0;
    for(int i=0;i<cnt;i++)
    {
        int r=res[i];
        f[r]=a[r];
        for(int j=0;j<i;j++)
        {
            int l=res[j];
            if(g[l][r]&&f[l]+a[r]>f[r])
            {
                pre[r]=l;
                f[r]=f[l]+a[r];
            }
        }
        if(f[k]<f[r]) k=r;
    }

    output(k);

    cout<<'\n'<<f[k]<<endl;

    return 0;
}