2312-Magical Girl Sayaka-chan

解法

まず，円ではなく直線上に並べること考えると，音符を音程でソートするのが最適になる．

円の場合は下の図のように，2つの直線に分けて考えることが出来る．

よって，音符を2つの直線に割り振る問題となる．

ゆえにdp[1本目の最後の音符番号][2本目の最後の音符番号]とすることで，
O(N^2)で計算できる．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
lli N,M,L;
lli S[110000];
lli K[110000];
lli sum[110001]; //累積和
lli dp[2200][2200];
inline lli calc(int a,int b){
	return (sum[b+1]-sum[a])/L;
}
lli solve(int back1,int back2){
	if(back1<back2)swap(back1,back2);
	if(dp[back1][back2]>=0)return dp[back1][back2];
	int now=max(back1,back2);
	if(now==N-1){
		return dp[back1][back2]=calc(K[min(back1,back2)],K[now]);
	}

	lli res=min(solve(now+1,back2)+calc(K[back1],K[now+1]),solve(back1,now+1)+calc(K[back2],K[now+1]));
	return dp[back1][back2]=res;
}
lli readint(){
	int t;
	scanf("%d",&t);
	return t;
}
int main(){
	N=readint();
	M=readint();
	L=readint();
	memset(dp,-1,sizeof(dp));
	REP(i,N){
		K[i]=readint();
		K[i]--;
	}
	std::sort(K,K+N);
	REP(i,M){
		S[i]=readint();
	}
	sum[0]=0;
	for(int i=1;i<=M;i++){
		sum[i]=sum[i-1]+S[i-1];
	}
	cout<<solve(0,0)<<endl;
}