[AtCoder-ARC073F]Many Moves

題目大意：
　　有一排n個格子和2枚硬幣。
　　現在有q次任務，每一次要你把其中一枚硬幣移到x的位置上，移動1格的代價是1。
　　兩枚硬幣不能同時移動，任務必須按次序完成。
　　現在告訴你兩枚硬幣初始狀態所在的位置a和b，問完成所有任務的最小代價。

思路：
　　很容易想到一個O(qn)的DP。
　　由于完成任務的次序確定，每個任務的位置也確定，我們可以用f[i][j]表示完成第i個任務后，一個硬幣在x[i]，一個硬幣在j的最小代價。
　　轉移方程為f[i][j]=min{f[i-1][j]+|x[i]-x[i-1]|},f[i][a[i-1]]=min{f[i-1][j]+|x[i]-j|}。
　　然而這樣還是會TLE，在AtCoder上只過了14/34的測試數據。
　　不難發現，在狀態轉移方程中，如果我們能去掉絕對值，里面的東西就能用線段樹維護。
　　而絕對值的取值只與硬幣的左右位置關系有關。
　　因此我們可以建2棵線段樹，一棵表示被轉移的狀態在目標狀態左邊，一棵表示在右邊。
　　左線段樹中每個葉子結點x[i-1]維護f[i-1][j]-x[i-1]的值，右線段樹每個葉子結點x[i-1]維護f[i-1][j]+x[i-1]的值。
　　看了一下榜，發現排在前面的基本上都是用樹狀數組做的。
　　然而用樹狀數組維護區間最值難道不是O(log^2 n)的嗎？
　　事實上我們可以發現線段樹上維護的東西只會越來越小，這樣我們可以直接在樹狀數組上修改，不用考慮原來的最小值沒了怎么辦。
　　然后我又在樹狀數組里面加了一個剪枝。
　　這樣隨隨便便就能拿Rank1。

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
typedef signed long long int int64;
inline unsigned getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register unsigned x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
inline int64 min(const int64 &a,const int64 &b) {
    return a<b?a:b;
}
const int64 inf=0x7ffffffffffffff;
const int N=200001;
int n;
class FenwickTree {
    private:
        int64 val[N];
        int lowbit(const int &x) const {
            return x&-x;
        }
    public:
        FenwickTree() {
            std::fill(&val[0],&val[N],inf);
        }
        void modify(int p,const int64 &x) {
            while(p<=n) {
                if(x<val[p]) {
                    val[p]=x;
                } else {
                    return;
                }
                p+=lowbit(p);
            }
        }
        int64 query(int p) const {
            int64 ret=inf;
            while(p) {
                ret=min(ret,val[p]);
                p-=lowbit(p);
            }
            return ret;
        }
};
FenwickTree ta;
class RevFenwickTree {
    private:
        int64 val[N];
        int lowbit(const int &x) const {
            return x&-x;
        }
    public:
        RevFenwickTree() {
            std::fill(&val[0],&val[N],inf);
        }
        void modify(int p,const int64 &x) {
            while(p) {
                if(x<val[p]) {
                    val[p]=x;
                } else {
                    return;
                }
                p-=lowbit(p);
            }
        }
        int64 query(int p) const {
            int64 ret=inf;
            while(p<=n) {
                ret=min(ret,val[p]);
                p+=lowbit(p);
            }
            return ret;
        }
};
RevFenwickTree tb;
int64 f[N];
inline void modify(const int &p,const int64 x) {
    if(x<f[p]) {
        f[p]=x;
        ta.modify(p,x-p);
        tb.modify(p,x+p);
    }
}
int main() {
    n=getint();
    int q=getint(),a=getint(),b=getint();
    std::fill(&f[0],&f[N],inf);
    modify(a,0);
    int64 sum=0;
    while(q--) {
        a=b;
        b=getint();
        sum+=abs(a-b);
        int64 t1=ta.query(b)+b,t2=tb.query(b)-b;
        modify(a,min(t1,t2)-abs(a-b));
    }
    int64 tmp=inf;
    for(register int i=1;i<=n;i++) {
        tmp=min(tmp,f[i]);
    }
    printf("%lld\n",tmp+sum);
    return 0;
}

原來的O(n^2)DP程序：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
inline unsigned getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register unsigned x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
inline unsigned min(const unsigned &a,const unsigned &b) {
    return a<b?a:b;
}
const unsigned N=200000;
unsigned long long f[2][N];
unsigned a[2];
int main() {
    unsigned n=getint(),q=getint();
    memset(f[0],0xff,n<<3);
    a[0]=getint()-1,f[0][getint()-1]=0;
    for(register unsigned i=1;i<=q;i++) {
        a[i&1]=getint()-1;
        memset(f[i&1],0xff,n<<3);
        for(register unsigned j=0;j<n;j++) {
            if(!~f[~i&1][j]) continue;
            f[i&1][j]=min(f[i&1][j],f[~i&1][j]+abs(a[i&1]-a[~i&1]));
            f[i&1][a[~i&1]]=min(f[i&1][a[~i&1]],f[~i&1][j]+abs(a[i&1]-j));
        }
    }
    unsigned long long ans=~0;
    for(register unsigned i=0;i<n;i++) {
        ans=min(ans,f[q&1][i]);
    }
    printf("%llu\n",ans);
    return 0;
}

?