Codeforces #721 Div2 : E. Partition Game

本番割とすんなり通してるな。
https://codeforces.com/contest/1527/problem/E

問題

整数列のコストを、以下のように定める。

• 整数列中に登場する各値に対し、最後に登場するindexから最初に登場するindexの総和

N要素の整数列Aが与えられる。
この整数列をK個の連続した部分列に分割することを考える。
総コストの最小値を求めよ。

解法

f(k,n) := 先頭n要素をk個に分割したときの総コストの最小値

区間加算・区間最大値を取れるSegtreeを考える。
初期状態としてSegtreeのn番目の要素にはf(k-1,n)を入れておく。
この状態から、f(k,n)をnの小さい順に埋めて行く。

基本的に、
f(k,n) := SegTree上の区間[0,n-1]の最小値 + n
とする。ただし、A[n]=A[m]となるn未満の最大のmがあるとき、左端は[0,m]の範囲にするとn-mだけコストが増える必要があるので、SegTreeに区間加算しよう。

int N,K;
int A[353535];
int pre[303030];
int P[303030];

ll dp[101][35353];

static ll const def=1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	MINUS(pre);
	FOR(i,N) {
		cin>>A[i];
		P[i]=pre[A[i]];
		pre[A[i]]=i;
	}
	
	dp[0][0]=0;
	FOR(i,N) dp[0][i+1]=1LL<<60;
	for(i=1;i<=K;i++) {
		SegTree_3<ll,1<<16> st;
		FOR(j,N) st.update(j,j+1,dp[i-1][j]);
		FOR(j,N) {
			if(P[j]>=0) st.update(0,P[j]+1,j-P[j]);
			dp[i][j+1]=st.getval(0,j+1);
		}
		
	}
	
	cout<<dp[K][N]<<endl;
	
	
}

まとめ

D問題の方が手間取ったな…。