Pro4

原始文件为 CPP 代码，本文是转换后的 Markdown 文件。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 305;

struct Edge
{
    int from, to, dist;
    Edge(int f, int t, int d) : from(f), to(t), dist(d){}
};

bool inq[maxn];
int dist[maxn];
int after[maxn];
vector<int> G[maxn];
vector<Edge> edges;

void add_edge(int from, int to, int dist)
{
    G[from].push_back(edges.size());
    edges.push_back(Edge{from, to, dist});
}

void bellman_ford(int n)
{
    queue<int> Q;
    for(int i = 0; i <= n; ++i)
    {
        Q.push(i); dist[i] = 0;
        inq[i] = true;
    }
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        inq[u] = false;

        for(int i = 0; i < G[u].size(); ++i)
        {
            Edge& e = edges[G[u][i]];
            if(dist[e.to] < dist[u] + e.dist)
            {
                dist[e.to] = dist[u] + e.dist;
                if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; }
            }
        }
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);

    for(int i = 1; i <= n; ++i) scanf("%d", &after[i]);

    for(int i = 0; i < n; ++i) add_edge(i, i+1, 1);
    for(int i = 3; i <= n; ++i) add_edge(i, i-3, -(3*after[i-1]+2) );
    for(int i = 3; i <= n; ++i) add_edge(i-3, i, 3*after[i-1]);

    add_edge(2, 0, -(2*after[1]+1) ); add_edge(0, 2, 2*after[1]);
    add_edge(n, n-2, -(2*after[n]+1) ); add_edge(n-2, n, 2*after[n]);

    bellman_ford(n);

    for(int i = 0; i < n; ++i)
        printf("%d ", dist[i+1] - dist[i]);
}