こっから先、本番は問題すら見てなかったんだけど、これノーヒントで解けたな…。
本番に挑めばよかった、もったいない。
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); }
まとめ
これは本番で解くべき問題だ…。