Codeforces #842 : Div2 F. Wonderful Jump

コードは意外に短い。
https://codeforces.com/contest/1768/problem/F

問題

Nマスの双六を考える。
各マスにはA[i]の値が書かれている。
i番→j番のマスに移動するとき、min(A[i],....A[j])*(j-i)^2のコストがかかる。
1番のマスから各マスに至る最小コストを求めよ。

解法

(j-i)^2は急激に大きくなることを用いる。

• 近距離(√max(A)あたり)の移動は総当たりする。
• 遠距離については、A[j]=1,2,3....√max(A)あたりを取る最寄りのA[j]を総当たりする。

int N;
int A[404040];
ll dp[404040];
int pre[404040];
const int DI=666;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		dp[i]=1LL<<60;
	}
	MINUS(pre);
	dp[0]=0;
	pre[A[0]]=0;
	cout<<0;
	for(i=1;i<N;i++) {
		int mi=A[i];
		for(j=1;j<min(i+1,DI);j++) {
			mi=min(mi,A[i-j]);
			dp[i]=min(dp[i],dp[i-j]+1LL*mi*j*j);
		}
		if(A[i]<=DI) {
			for(j=i-1;j>=0;j--) {
				dp[i]=min(dp[i],dp[j]+1LL*A[i]*(i-j)*(i-j));
				if(A[j]<=A[i]) break;
			}
		}
		
		for(j=1;j<=DI;j++) if(pre[j]>=0) {
			dp[i]=min(dp[i],dp[pre[j]]+1LL*j*(i-pre[j])*(i-pre[j]));
		}
		cout<<" "<<dp[i];
		pre[A[i]]=i;
	}
	cout<<endl;
	
}

まとめ

考察を聞いてしまえば楽な問題。
自力で思いつくのはちょっとしんどい。