[ICPC 2018 Nanjing Onsite B]Tournament

Link

Solution

首先需要知道,用一个stadium覆盖n个位置,肯定建在中间的那个上。
普通的DP,f[i][j]表示前i个放了j个stadium,将前i个都覆盖了的最小代价,然后f[i][j]=\min (f[k][j-1]+cost(k+1,i))。这个cost就是用一个stadium覆盖[k+1,i]的最小代价。虽然这样没有保证被不同的stadium覆盖的地点一定是被离它最近的那个覆盖,但是考虑到最小的答案一定是那样的情况,所以这样DP正确性没有问题。
接着就wqs二分+决策单调性。。会了就是模板了。。
各种决策单调性还要好好学一学……

Code

const int XN=3e5+11;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN];
    static long long sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    auto DP=[&](long long C)->std::pair<long long,int> {
        static std::pair<long long,int> f[XN];
        auto Cost=[&](int l,int r) {//建站覆盖[l,r]
            int mid=(l+r)/2;
            return sum[r]-2*sum[mid-1]+sum[l-1]+(long long)a[mid]*(2*mid-l-r-1);
        };

        auto Calc=[&](int j,int i)->std::pair<long long,int> {
            return std::make_pair(f[j].first+Cost(j+1,i)+C,f[j].second+1);
        };

        auto Boundary=[&](int k1,int k2)->int {//k2 better than k1 if p>=x
            int L=k2+1,R=n+1;
            while(L!=R) {
                int M=(L+R)/2;
                if(M!=n+1 && Calc(k1,M)<=Calc(k2,M))
                    L=M+1;
                else
                    R=M;
            }
            return L;
        };

        static std::pair<int,int> Q[XN];
        static int head,tail;
        Q[(tail=head=0)++]={0,0};
        for(int i=1;i<=n;++i) {
            while(tail-head>=2 && Calc(Q[head].first,i)>=Calc(Q[head+1].first,i))
                head++;
            f[i]=Calc(Q[head].first,i);
            while(tail-head>=2 && (Q[tail-1].second==n+1 || Calc(Q[tail-1].first,Q[tail-1].second)>=Calc(i,Q[tail-1].second)))
                tail--;
            Q[tail]={i,Boundary(Q[tail-1].first,i)};
            tail++;
        }
        return f[n];
    };

    long long L=0,R=sum[n];
    while(L!=R) {
        long long M=(L+R)/2;
        if(DP(M).second<=m)
            R=M;
        else
            L=M+1;
    }

    long long Ans=DP(L).first-L*m;
    std::cout<<Ans<<'\n';
    return 0;
}

发表评论

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