BZOJ2259 新型计算机

本来按 lc 的多项式课件上写的 2259 来的,结果好像他把 cogs 上的题写成 BZOJ 了还是什么?
好吧反正这题和多项式没关系, cogs 也上不了我也没办法

题意

从前往后先读取第一个数字 S1,然后顺序向后读入 S1 个数字。接着再读一个数字 S2,顺序向后读入 S2 个数字…… 依此类推。只有所有的数恰好读完的序列才是合法的。
给出一个输入序列,可以对于序列中的任意一个数进行修改,使修改后的序列是合法序列。求操作的最小代价。设某个位置但是数是 x,把他变成 y 的代价是 abs (x-y)

题解

一开始怎么看样例都不对,感觉要 2 才行
最后才发现把第一个改成 3 就行了,估计没有比我更傻的了

考虑使用最短路做
当 $i$ 满足 $i+a[i]+1>N+1$ 时,说明会超出,应该向 $N+1$ 连一条 $i+a[i]-N$ 的边
否则到达的地方在数列内,可以向 $i+a[i]+1$ 连一条 $0$ 的边
但是我们时可以调整的,也就是可以通过加减将下一个点左右移动,于是枚举左右,由 $j$ 向 $j-1,j+1$ 连一条 $1$ 的边
判断一下不连重边就行

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

#define MAX_N 1000007
#define INF 1e9
#define reg register
typedef long long ll;

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {if (c == '-') y = -1; c = getchar();}
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

int N, a[MAX_N];
int head[MAX_N], to[MAX_N * 3], nxt[MAX_N * 3], cap;
ll dis[MAX_N * 3], d[MAX_N];
bool vis[MAX_N], visl[MAX_N], visr[MAX_N];

struct node {
    int u;
    ll w;

    bool operator < (const node &rhs) const {
        return w > rhs.w;
    }
};
std::priority_queue<node> q;

inline void addEdge (int u, int v, ll w) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
    dis[cap] = w;
}

inline void input () {
    read(N);
    for (int i = 1; i <= N; ++i)
        read(a[i]);
}

inline void init () {
    for (int i = 1; i <= N; ++i)
        if (i + a[i] > N) {
            addEdge(i, N + 1, i + a[i] - N);
        } else {
            addEdge(i, i + a[i] + 1, 0);
            int j = i + a[i] + 1;
            while (j > i + 1 && !visl[j])
                addEdge(j, j - 1, 1), visl[j] = true, j--;
            j = i + a[i] + 1;
            while (j <= N && !visr[j])
                addEdge(j, j + 1, 1), visr[j] = true, j++;
        }
}

inline void solve () {
    for (int i = 1; i <= N + 1; ++i)
        d[i] = INF;
    memset(vis, false, sizeof(vis));
    d[1] = 0;
    q.push((node){1, 0});
    while (!q.empty()) {
        node x = q.top(); q.pop();
        if (vis[x.u]) continue;
        vis[x.u] = true;
        for (int i = head[x.u]; i; i = nxt[i]) {
            if (d[to[i]] > d[x.u] + dis[i]) {
                d[to[i]] = d[x.u] + dis[i];
                q.push((node){to[i], d[to[i]]});
            }
        }
    }
    printf("%lld\n", d[N + 1]);
}

int main () {
    input();
    init();
    solve();
    return 0;
}

引用资料

clover_hxy 博客上的题目大意

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注