BZOJ2259 [Oibh]新型計算機 題解

題目傳送門

提供兩種做法

1.Dijstra最短路

正常連邊后,對于每個位置 \(i\) 都加上 \(i-1->i\) 和 \(i->i+1\) ,長度為 \(1\) 的邊,相當于先按照原方法走再改動。

不過題目中要求改動后的數必須是自然數(也就是正整數),所以不是所有點都可以加,必須逐個判斷能否改動。

然后跑一個堆優化Dijkstra即可。

$Code\ by\ $ @wsy_jim

%%%

#include<iostream>#include<cstdio>#include<algorithm>#include<string>#include<cmath>#include<vector>#include<map>#include<queue>#include<deque>#include<set>#include<stack>#include<bitset>#include<cstring>#define ll long long#define pii pair<int,int>using namespace std;const int INF=0x3f3f3f3f,N=1000010;int e[4*N],ne[4*N],idx,h[N],w[4*N],n,ls[N],rs[N];inline int read(){    int x=0,y=1;char c=getchar();    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();    return x*y;}void add(int a,int b,int c){    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;}namespace dijkstra{    int dist[N];    bool vis[N];    int dijkstra(int st,int ed){        memset(dist,0x3f,sizeof dist);        priority_queue<pii,vector<pii>,greater<pii> > q;        dist[st]=0;        q.push(make_pair(0,st));        while(q.size()){            pii op=q.top();            q.pop();            int dis=op.first,ver=op.second;            if(vis[ver]) continue;            vis[ver]=1;            for(int i=h[ver];~i;i=ne[i]){                int j=e[i];                if(dist[j]>dist[ver]+w[i]){                    dist[j]=dist[ver]+w[i];                    q.push(make_pair(dist[j],j));                }             }        }        if(dist[ed]==0x3f) return -1;        return dist[ed];    }}int main(){    memset(h,-1,sizeof h);    n=read();    for(int i=1,k;i<=n;i++){        k=read();        if(i+k<=n) add(i,i+k+1,0);        else add(i,n+1,i+k-n);        for(int j=i+1;j<=i+k+1&&j<=n&&!ls[j];j++)ls[j]=1,add(j,j-1,1);for(int j=i+k+1;j<=n&&!rs[j];j++)rs[j]=1,add(j,j+1,1);    }    // for(int i=1;i<=n;i++){    //     for(int j=h[i];~j;j=ne[j]) printf("%d %d  ",e[j],w[j]);    //     printf("\n");    // }    ll ans=dijkstra::dijkstra(1,n+1);    printf("%lld\n",ans);        return 0;}

2.樹狀數組維護DP

設 \(f[i]\) 表示處理 \(i\) 到 \(n\) 的最優答案。
易得

\[f[i] = min ( f[j] + abs(j - i - 1 - a[i]) )\ \ \ (i<j<n)\]

把這個式子打開

\[f[i] = min(f[j]+j)-(i+1+a[i]) (j ≥ a[i]+i+1)\]\[f[i] = min(f[j]-j)+(i+1+a[i]) (j<a[i]+i+1)\]

然后用樹狀數組維護 \(f[j]+j\) 和 \(f[j]-j\) 即可

\(Code\)

#include<algorithm>#include<bitset>#include<cctype>#include<cerrno>#include<clocale>#include<cmath>#include<complex>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<deque>#include<exception>#include<fstream>#include<functional>#include<limits>#include<list>#include<map>#include<iomanip>#include<ios>#include<iosfwd>#include<iostream>#include<istream>#include<ostream>#include<queue>#include<set>#include<sstream>#include<stack>#include<stdexcept>#include<streambuf>#include<string>#include<utility>#include<vector>#include<cwchar>#include<cwctype>#include<chrono>#include<random>#include<unordered_map>using namespace std;#define ll long long#define ull unsigned long long#define rll register long long#define ri register int#define il inline//#define int long longconst int INF=0x3f3f3f3f,N=1e6+10;int n,t;int ins[N];int f[N];int t1[N],t2[N];il ll read(){    ll x=0,y=1;    char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')            y=-1;        c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';        c=getchar();    }    return x*y;}il int lowbit(int x){    return x&(-x);}il int query1(int x){    int mid=INF;    x=(n+1)-x;    if(x>n||x<=0)        return mid;    while(x){        mid=min(mid,t1[x]);        x-=lowbit(x);    }    return mid;}il int query2(int x){    int mid=INF;    if(x>n||x<=0)        return mid;    while(x){        mid=min(mid,t1[x]);        x-=lowbit(x);    }    return mid;}il void wh(int x){    int mid=x;    while(mid<=n){        t2[mid]=min(t2[mid],f[x]-x);        mid+=lowbit(mid);    }    mid=(n+1)-x;    while(mid<=n){        t1[mid]=min(t1[mid],f[x]+x);        mid+=lowbit(mid);    }}signed main(){    n=read();    memset(t1,0x3f,sizeof(t1));    for(ri i=1;i<=n;i++)        ins[i]=read();    for(ri i=n;i>=1;i--){        f[i]=abs(n-i-ins[i]);        t=ins[i]+i+1;        if(t<n)            f[i]=min(f[i],query1(t)-t);        f[i]=min(f[i],query2(t)+t);        wh(i);    }    printf("%d",f[1]);    return 0;}