SCPC2016재활용

1. 재활용

절대 안돌아갈것 같은 MN^2이 돌아간다. 일단 MN^2으로 풀고, 점화식 형태가 Divide and Conquer Optimization같아서 적용해봤는데 잘 된다.

dp[i][j] = i개의 쓰레기통으로 [0,j]의 집을 커버할때 (집:쓰레기통) 거리들 합의 최소

#include "Core.h"
//#include "FastIO.h"
#include "PrettyIO.h"
//#include "PrettyDebug.h"

int n,m;
Arr<int> a;
Arr<Arr<int>> dp,c;

int& f(int i, int j){
	static int _0=0, _inf=inf<int>();
	if(j==-1) return _0;
	if(i==-1) return _inf;
	return dp[i][j];
}

void dnc(int i, int s, int e, int ks, int ke){
	int mid=(s+e)/2, kk=ks;
	hfor(k,ks,ke){
		if(f(i,mid) > f(i-1,k)+c[k+1][mid])
			f(i,mid)=f(i-1,k)+c[k+1][mid], kk=k;
	}
	if(e-s>1){
		dnc(i,s,mid,ks,kk+1);
		dnc(i,mid,e,kk,ke);
	}
}

signed main(){
	int t; cin>>t;
	cfor(ti,1,t){
		cout<<"Case #"<<ti<<endl;
		cin>>n>>m;
		a=cinints(n);
		sort(all(a));
		dp=ARR(m,n,inf<int>());
		c=ARR(n,n,0ll);
		rep(i,n){
			int l=0,r=0;
			cfori(j,0,i){
				l+=a[j];
				if((i-j+1)%2)
					l-=a[(i+j)/2];
				c[j][i]=r-l;
				if((i-j+1)%2)
					r+=a[(i+j)/2];
			}
		}
		rep(i,m) dnc(i,0,n,-1,n-1);
		cout<<dp[m-1][n-1]<<endl;
	}
}