CSP201809-4 再卖菜

CSP201809-4 再卖菜
- 60分dfs
- 100分建立差分约束系统

这场打完就忘记了。当时这题一直在想怎么建立差分约束系统，最后没建出来0分，队友搜索暴力剪纸可能还有记忆化过的，其他人有的都是搜索拿的几十分，
用最暴力的写法直接搜即可。

60分dfs

菜的价格在1~100之间，直接dfs枚举菜的价格即可。300^n复杂度?其实减枝能剪掉很多。

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 310;

int n, a[MAXN], b[MAXN];

bool flag = false;

void dfs(int step) {
    int i = 0;
    if(flag) {
        return ;
    }
    if(step == n + 1) {
        bool ok = true;
        if((b[1] + b[2]) / 2 != a[1] || (b[n] + b[n - 1]) / 2 != a[n]) {
            ok = false;
        }
        for(i = 2; i <= n - 1; i++ ) {
            if((b[i - 1] + b[i] + b[i + 1]) / 3 != a[i]) {
                ok = false;
            }
        }
        if(!ok) {
            return ;
        }
        for(i = 1; i <= n; i++ ) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", b[i]);
        }
        puts("");
        flag = true;
        return ;
    }
    for(i = 1; i <= 130; i++ ) {
        b[step] = i;
        if(step == 2) {
            if(a[1] != (b[1] + b[2]) / 2) {
                continue;
            }
        } else {
            if(step >= 3) {
                if((b[step] + b[step - 1] + b[step - 2]) / 3 != a[step - 1]) {
                    continue;
                }
            }
        }
        if(step <= n) {
            dfs(step + 1);
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++ ) {
        scanf("%d", &a[i]);
    }
    dfs(1);

    return 0;
}

100分建立差分约束系统

在现场的时候我就一直在想怎么建。三元不等式不会化简单。现在才知道，另si = x1 + x2 + ... xn
这样例如x2 + x3 + x4 就可以用s4 - s1代替。这样题目获得的是a数组。我们有s数组，不等式直接建立差分约束系统即可。具体不等式见注释
学过差分约束的讲到这里就够了，不会的需要补一补基础。

/**
等式的确立是由于向下取整
a1 * 2 <= x1 + x2 <= a1 * 2 + 1
a2 * 3 <= x1 + x2 + x3 <= a2 * 3 + 2
...

an * 2 <= x[n - 1] + x[n] <= an * 2 + 1

let
si = x0 + x1 + x2 + ... + xn

change xi

[1]
such as a1 * 2 <= s2 - s0
        a1 * 2 + 1 <= s0 - s2
[2]
so
    把上面x数组改s即可。
    0 <==> 3
    ...
    ...
    ...
    n - 3 <==> n
[3]
xi >= 1

for each xi - xj >= k add_edge(j -> i, w) find the longest path

*/

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 3050;
const int MAXM = MAXN * MAXN;

int n, m, first[MAXN], sign, a[MAXN];

struct Edge {
    int to, w, next;
} edge[MAXM];

void init() {
    memset(first, -1, sizeof(first));
    sign = 0;
}

void add_edge(int u, int v, int w) {
    edge[sign].to = v;
    edge[sign].w = w;
    edge[sign].next = first[u];
    first[u] = sign++;
}

int dist[MAXN], inq[MAXN];

void spfa() {
    queue<int>que;
    for(int i = 0; i <= n; i++ ) {
        que.push(i);
        dist[i] = 0, inq[i] = 0;
    }
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        inq[now] = 0;
        for(int i = first[now]; ~i; i = edge[i].next) {
            int to = edge[i].to, w = edge[i].w;
            if(dist[to] < dist[now] + w) {
                dist[to] = dist[now] + w;
                if(!inq[to]) {
                    que.push(to);
                    inq[to] = 1;
                }
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    init();
    for(int i = 1; i <= n; i++ ) {
        scanf("%d", &a[i]);
    }
    for(int i = 0; i <= n - 3; i++ ) {
        add_edge(i + 3, i, -(a[i + 2] * 3 + 2)); /// x[i] - x[i + 3] >= -(a[i+2] * 3 + 2)
        add_edge(i, i + 3, a[i + 2] * 3);        /// x[i +3] - x[i] >= (a[i+2] * 3)
    }
    add_edge(2, 0, -(a[1] * 2 + 1));        ///s0-s2 >= -(a[1] * 2 + 1)
    add_edge(0, 2, a[1] * 2);               ///s2-s0 >= (a[1] * 2)
    add_edge(n, n - 2, -(a[n] * 2 + 1));    ///sn-s[n-2] >= -(a[n] * 2 + 1)
    add_edge(n - 2, n, a[n] * 2);           ///s[n-2]-sn >= (a[n] * 2)
    for(int i = 1; i <= n; i++ ) {          /// si - s[i-1] >= 1
        add_edge(i - 1, i, 1);
    }
    spfa();
    a[1] = dist[1];
    for(int i = 2; i <= n; i++ ) {
        a[i] = dist[i] - dist[i - 1];
    }
    for(int i = 1; i <= n; i++ ) {
        if(i != 1) {
            printf(" ");
        }
        printf("%d", a[i]);
    }
    puts("");


    return 0;
}