AOJ2603 Time Table

AOJ

バスをm本走らせてn人拾う時の待ち時間の和の最小値を求める問題






とりあえずバス停の場所を時間からひくといつ出発するとちょうどかがわかるので、それをsortしてTiとおく

まず何も考えずに愚直なdpの式を立てると
dp[i][d] = min{0<=j<=i}(dp[j][d-1] + sum{j+1<=k<=i}(t[i]-t[j]) )となり、変形すると

dp[i][d] = i * t[i] - Si + min{0<=j<=i}(dp[j][d-1]+Sj - j * Ti) (ただしSiはTiの累積和)

となり、iとjがいい感じに分離できる。

  • jが単調減少, Tiが広義単調増加するので蟻本に載っている形のconvex-hull trickを使うことで加速できる
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

int dp[2010][2010];
int s[2010],t[2010];

ll f(int j,int pos,int d){return dp[d][j]+s[j]-j*pos;}

bool ng(int t1,int t2,int t3,int d){
    ll a1=-t1, b1=dp[d][t1]+s[t1];
    ll a2=-t2, b2=dp[d][t2]+s[t2];
    ll a3=-t3, b3=dp[d][t3]+s[t3];
    return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}

int p[2010];
int a,n,m;
int l,r;
int deq[2010];

int main(){
    scanf("%d%d%d",&a,&n,&m);
    rep(i,a)scanf("%d",p+i);
    rep(i,n){int y;scanf("%d%d",t+i,&y);t[i]-=p[y-1];}
    sort(t,t+n);

    rep(i,n) rep(j,i) dp[0][i+1]+=t[i]-t[j];    
    rep(i,n) s[i+1]=s[i]+t[i];

    for(int j=1;j<m;++j){
	l=0,r=0;
	for(int i=1;i<=n;++i){
	    while(l+1<r && ng(deq[r-2],deq[r-1],i,j-1)) --r;
	    deq[r++]=i;
	    while(l+1<r && f(deq[l],t[i-1],j-1) >= f(deq[l+1],t[i-1],j-1)) ++l;
	    dp[j][i]=i*t[i-1]-s[i]+f(deq[l],t[i-1],j-1);
	}
    }
    printf("%d\n",dp[m-1][n]);
    return 0;
}