201809-4 再卖cai

思路

典型的差分约束问题，只不过转化起来有点麻烦，注意转化的边界情况就行

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N = 310;
const int M = 3 * N;
int h[N], e[M], ne[M], w[M], idx;
int n;
int b[N];
int d[N];
bool st[N];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa(){
    memset(d, -0x3f, sizeof(d));
    d[0] = 0;
    queue<int> q;
    q.push(0);
    st[0] = true;
    while(q.size()){
        int u = q.front();
        st[u] = false;
        q.pop();
        for(int i = h[u];i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] < d[u] + w[i]){
                d[j] = d[u] + w[i];
                if(!st[j]){
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main(){
    cin>>n;
    memset(h, -1, sizeof(h));
    for(int i = 1;i<=n;i++)cin>>b[i];
    for(int i = 2;i){
        add(i - 2, i + 1, 3 * b[i]);
        add(i + 1, i - 2, -(3 * b[i] + 2));
    }
    for(int i = 0;i < n; i++){
        add(i, i + 1, 1);
    }
    add(0, 2, 2 * b[1]);
    add(2, 0, -(2 * b[1] + 1));
    add(n - 2, n, 2 * b[n]);
    add(n, n - 2, -(2 * b[n] + 1));
    spfa();
    for(int i = 1;i<=n;i++){
        if(i != 1)cout<<" ";
        cout<1];
    }
}