Codeforces #1023 : Div2 F2. Cycling (Hard Version)

こちらもコードは短め。
https://codeforces.com/contest/2107/problem/F2

問題

主人公の前にN人の人がおり、彼らを抜かして先頭に行きたい。
i番目の人の速さはA[i]である。

主人公は以下の処理を行える。

• i番目の人を、コストA[i]かけて抜く
• A[i]とA[j]をswapする。その際、コストは|A[j]-A[i]|かかる。

Aのprefixごとに、主人公が先頭にいく最小コストを求めよ。

解法

もし目の前の人の速さが最少なら、追い抜くたびに前後の人の速さをスワップすることで、その速さの値を使いまわせる。
なお、実は考察すると数列中の最小値から+20の範囲までの範囲の速さだけ使えば総コストの最小値を求められる。
よってその値をよそから持ってきた場合のコストをそれぞれ求めよう。

int T,N;
const int SZ=1<<20;
ll A;
ll dp[1<<20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		dp[0]=0;
		map<int,int> M;
		FOR(i,N) dp[i+1]=1LL<<60;
		
		for(i=1;i<=N;i++) {
			cin>>A;
			dp[i]=min(dp[i],1LL*i*(A+1)-1);
			
			if(M.size()) {
				int mi=M.begin()->first;
				for(x=mi;x<=mi+20;x++) if(M.count(x)) {
					y=M[x];
					// ここまでその値を使う
					chmin(dp[i],dp[y]+1LL*(i-y)*(x+2));
					// 受け渡す
					chmin(dp[i],dp[y]+1LL*(i-y)*(A+1)-1);
				}
			}
			M[A]=i;
			cout<<dp[i]<<" ";
		}
		cout<<endl;
	}
}

まとめ

この考察は思いつかんわ…。