Codeforces #1001 : F. Traveling Salescat

なるほど…。
https://codeforces.com/contest/2062/problem/F

問題

N個の点があり、それぞれパラメータが2つ(A[i],B[i])ずるある。
2点間(i,j)の距離を、max(A[i]+B[j],A[j]+B[i])とする。
N点中K点のパスの距離の最小値を、K=2～Nについて求めよ。

解法

X[i]=(A[i]+B[i])/2、Y[i]=(A[i]-B[i])/2と座標変換すると、max(A[i]+B[j],A[j]+B[i])=X[i]+X[j]+|Y[i]-Y[j]|となる。

Yをあらかじめ昇順にソートしたとする。
この状態でK点選んだ時、番号の最小値がi,最大値がj、かつK点のパスの両端の番号がa,bとすると

• K個のX[i]のうち、X[a],X[b]が1回、それ以外のX[i]は2回ずつ距離に計上される。
• K個のX[i]のうち、2*(Y[j]-Y[i])-(Y[b]-Y[a])が距離に計上される。

これを踏まえDPを行っていく。
dp(n,k,mask) := prefix n点のうちk点選んだ時、選んだ点のX[i]の2倍と-Y[i]の和の最小値。ただしa,bに相当する2点を選択済みであればmaskに反映される。またその分X[a],X[b],Y[b],Y[a]加減算する。

としてk点を選んでいこう。

int T;
int N;
pair<ll,ll> P[3030];

ll dp[3030][4];
ll ret[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>x>>y;
			P[i]={x-y,x+y};
		}
		sort(P,P+N);
		FOR(i,N+2) dp[i][0]=dp[i][1]=dp[i][2]=ret[i]=1LL<<60;
		dp[0][0]=0;
		FOR(i,N) {
			ll A=P[i].second,B=P[i].first;
			for(j=N-1;j>=0;j--) FOR(k,3) if(dp[j][k]<1LL<<59) {
				// 1
				if(j==0) {
					chmin(dp[j+1][k+1],dp[j][k]+A-B);
				}
				else if(k==0) {
					chmin(dp[j+1][k+1],dp[j][k]+A+B);
				}
				else {
					chmin(dp[j+1][k+1],dp[j][k]+A-B);
					if(k==1) chmin(ret[j+1],dp[j][k]+A+B);
				}
				// 2
				if(j==0) {
					chmin(dp[j+1][k],dp[j][k]+A*2-2*B);
				}
				else {
					chmin(dp[j+1][k],dp[j][k]+A*2);
					if(k==2) chmin(ret[j+1],dp[j][k]+A*2+2*B);
				}
			}
		}
		for(i=2;i<=N;i++) cout<<ret[i]/2<<" ";
		cout<<endl;
		
	}
}

まとめ

最初の座標変換が思いつかないと手が出ないな…。