阿祁的部落格

ZeroJudge f638 - 支點切割 解題心得( 題目 )

解題概念:前綴和

解題方法:我們先把前綴和(記做ls)跟後綴和(記做rs)做一次，然後分別對於他們兩個再做前綴和(lss)、後綴和(記做rss)，這樣的好處是，如果先假設今天陣列範圍是0-n，則如果假設我要切陣列第3個，我們求的a0*3+a1*2+a2*1就是(a0+a1+a2)+(a0+a1)+(a0)=ls[2]+ls[1]+ls[0]=lss[2]，因右邊概念一樣，我們就可以在O(1)的時間記錄一切點的cost，線性去尋找哪個比較大。

再來如果範圍不是全部呢?假設我們切i，我們左邊其實就是lss[i-1]-lss[l-1]-ls[l-1]*(i-l)，原因是下圖的三角形減長方形，他會互消變成我們要的答案，所以一個點的查詢也是O(1)。

Java參考程式碼(註:下面程式為方便實作是1-based)

import java.io.*;
public class d004 {
    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static int ret,r,k;
    public static long rt=0;
    public static int[] mp=new int[50005];
    public static long[] ls=new long[50005];
    public static long[] rs=new long[50005];
    public static long[] lss=new long[50005];
    public static long[] rss=new long[50005];
     public static void main(String[] args) throws Exception{
        final int n=orz();
        k=orz();
        for(int i=1;i<=n;i++)mp[i]=orz();
        ls[0]=lss[0]=0;
        rs[n+1]=rss[n+1]=0;
        for(int i=1;i<=n;i++)ls[i]=ls[i-1]+mp[i];
        for(int i=1;i<=n;i++)lss[i]=lss[i-1]+ls[i];
        for(int i=n;i>0;i--)rs[i]=rs[i+1]+mp[i];
        for(int i=n;i>0;i--)rss[i]=rss[i+1]+rs[i];
        cut(1,n,0);
        System.out.println(rt);
    }
    public static void cut(int l,int r,int c) {
        if(c==k||l+1>=r)return;
        long min=1L<<60,t;
        int p=-1;
        for(int i=l+1;i<r;i++) {
            t=Math.abs(lss[i-1]-lss[l-1]-ls[l-1]*(i-l)-rss[i+1]+rss[r+1]+rs[r+1]*(r-i));
            if(t<min) {
                min=t;
                p=i;
            }
        }
        rt+=mp[p];
        cut(l,p-1,c+1);
        cut(p+1,r,c+1);
    }
    public static int orz() throws Exception{
        ret=0;
        r=br.read();
        while(r>47&&r<58) {
            ret*=10;
            ret+=(r&15);
            r=br.read();
        }
        return ret;
    }
}