Codeforces #655 Div2 E. Omkar and Last Floor

なんか後半解いてる人少ないと思ったらunratedだった回か。
https://codeforces.com/contest/1372/problem/E

問題

N*Mの0/1のマトリックスを考える。
各行は、いくつかのセグメントに分割されている。
各セグメント、1要素だけ1を配置できるとする。

マトリックスのスコアは、各列における総和の二乗和とする。
最適な配置をしたとき、スコアの最大値を求めよ。

解法

f(L,R) := L列からR列のうち、これらの列に完全に含まれるセグメントに関するスコアの最大値
とする。
L...R列のうち1列Mを総当たりする。
M列に可能な限り1を集めた場合を考え、あとはf(L,M-1)とf(M+1,R)の和を再帰的にとっていけばよい。

int N,M;
int K[101];
int L[101][101],R[101][101];
int T[101][101];

int memo[101][101];

int hoge(int LL,int RR) {
	if(LL>RR) return 0;
	if(memo[LL][RR]>=0) return memo[LL][RR];
	int ret=0;
	int i;
	for(int x=LL;x<=RR;x++) {
		int num=0;
		FOR(i,N) {
			int t=T[i][x];
			if(L[i][t]>=LL&&R[i][t]<=RR) num++;
		}
		ret=max(ret,num*num+hoge(LL,x-1)+hoge(x+1,RR));
	}
	
	
	return memo[LL][RR]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>K[i];
		FOR(j,K[i]) {
			cin>>x>>y;
			L[i][j]=x-1;
			R[i][j]=y-1;
			for(k=L[i][j];k<=R[i][j];k++) T[i][k]=j;
		}
	}
	
	MINUS(memo);
	cout<<hoge(0,M-1)<<endl;
	
}

まとめ

問題文が若干難しい。