TopCoder SRM 714 Div2 Hard Saleswoman

ちょっと手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=14590

問題

数直線上にN人の人iがおり、それぞれの座標P[i]が与えられる。
P[i]は昇順である。

各人は商品を売りたいまたは買いたい。
そこで、数直線上を移動しつつ、商品の売買を行い、買いたい人の希望をすべてかなえるようにしたい。
プレイヤーは初期状態で商品を持っておらず、座標0にいる。
購入希望者の希望をすべてかなえ、最終的にP[N]の位置にたどり着くようにする最小の移動量を求めよ。

解法

通過した場所にいる商品を売りたい人の願いはすべてかなえて買い取ってしまってよい。
逆に買いたい人に対しては、商品が不足していると買い取れない。
その場合、もっと先の座標にいる人のところまで行って商品を仕入れ、戻ってきて売ることにしよう。

だとすると、物を売る際、あとでの出戻りの移動量を抑えるため、出来る丈手前にいる人の願いから順にかなえるとよい。
よって以下を考えよう。
f(a,b,x) := 物を買いたい人のうち願いを満たせていない最小の番号がa、物を売りたい人のうち訪問した最大の番号がb、xは現在位置がa,bのどちらかを示す、というような状態に到達する最小移動量

今b番のところまで移動して仕入れた商品で、a番までの人の買いたい量を賄える場合、a番のところまで戻って売ってもよいし、(b+1)番のところまで足を延ばしてもう少し仕入れに行ってもよい。
この要領でDPすると、O(N^2)で解ける。

int dp[555][555][2];
int PS[555],NS[555];

class Saleswoman {
	public:
	int minMoves(vector <int> pos, vector <int> delta) {
		
		int i,x,y;
		int N=pos.size();
		FOR(x,500) FOR(y,500) dp[x][y][0]=dp[x][y][1]=1<<30;
		dp[0][0][0]=pos[0];
		
		for(i=0;i<N;i++) {
			PS[i]=(i?PS[i-1]:0)+max(delta[i],0);
			NS[i]=(i?NS[i-1]:0)-min(delta[i],0);
		}
		
		FOR(y,N) FOR(x,y+1) {
			if(x==y) {
				if(y==N-1) continue;
				if(PS[x]>=NS[x]) {
					dp[x+1][y+1][1]=min(dp[x+1][y+1][1],min(dp[x][y][0],dp[x][y][1])+pos[y+1]-pos[y]);
				}
				else {
					dp[x][y+1][0]=min(dp[x][y+1][0],min(dp[x][y][0],dp[x][y][1])+pos[y+1]-pos[y]);
				}
			}
			else {
				if(PS[y]>=NS[x]) dp[x][y][1]=min(dp[x][y][1],dp[x][y][0]+pos[y]-pos[x]);
				if(NS[x+1]<=PS[y]) dp[x+1][y][1]=min(dp[x+1][y][1],dp[x][y][1]+pos[x+1]-pos[x]);
				
				if(y<N-1) {
					dp[x][y+1][0]=min(dp[x][y+1][0],dp[x][y][0]+pos[y+1]-pos[y]);
					dp[x][y+1][0]=min(dp[x][y+1][0],dp[x][y][1]+pos[y+1]-pos[x]);
				}
			}
		}
		
		return min(dp[N-1][N-1][0],dp[N-1][N-1][1]);
	}
}

まとめ

AtCoderでもう少し面倒な(SegTree/RMQを使う)バージョンを見たね。