kmjp's blog

競技プログラミング参加記です

Typical DP Contest : L - 猫

こっから先、本番は問題すら見てなかったんだけど、これノーヒントで解けたな…。
本番に挑めばよかった、もったいない。
http://tdpc.contest.atcoder.jp/tasks/tdpc_cat

問題

N匹の猫が一直線上に並んでいる。
それぞれの並び順は変えられないが、距離は変えることができる。
猫iと猫jの距離が1以下の場合、猫群の幸福度がF[i][j]上昇する。
猫群の幸福度を最大化せよ。

解法

猫を端から順に並べていく。
X番目の猫からY(>X)番目までが距離1にいる場合について幸福度を計算していく。
X番目の猫からY番目までが距離1にいる場合、(X+1)番目の猫からY番目までは確実に距離1にいる点に注意。
N<=1000でO(N^3)だけど0.7sぐらいで間に合った。

int N;
int F[1001][1001];
int sum[1001][1001];
int dpdp[1001][1001];

void solve() {
	int f,r,i,j,k,l, x,y,z,mask=0;
	
	cin>>N;
	FOR(x,N) FOR(y,N) F[x][y]=GETi();
	FOR(x,N) for(y=x+1;y<N;y++) sum[x][y]=sum[x][y-1]+F[x][y];
	
	FOR(x,N) FOR(y,N) dpdp[x][y]=-1<<30;
	dpdp[0][0]=0;
	FOR(x,N) {
		for(y=x-1;y<N;y++) {
			for(z=y;z<N;z++) {
				dpdp[x+1][z]=max(dpdp[x+1][z],dpdp[x][y]+sum[x][z]);
			}
		}
	}
	int ma=-1<<30;
	FOR(y,N) ma=dpdp[N][y];
	return _P("%d\n",2*ma);
}

まとめ

これは本番で解くべき問題だ…。