Typical DP Contest L:猫
解法
dp[i][j]:i番目まで決めて,直前のj+1匹の猫(i番目の猫を含む)が距離1未満で密集してる感じのときの幸福度の最大値.
とした.
直前n匹が距離1未満で密集していたとすると,次の猫の場所を決めるときには直前n~0匹について距離1未満となるような場所に配置することをそれぞれ考えればよい.
dp[i][j](j>0)を更新するときは、
dp[i][j]=min{dp[i-1][k]|j-1<=k
コード
#include<bits/stdc++.h> using namespace std; const int INF=1001001001; int N; int f[1000][1000]; int dp[1001][1001]; int sum(int n,int l,int r){ return f[n][r]-(l?f[n][l-1]:0); } int main(){ scanf("%d",&N); for(int i=0;i<N;i++) for(int j=0;j<N;j++) scanf("%d",&f[i][j]); for(int i=0;i<N;i++){ for(int j=1;j<N;j++)f[i][j]+=f[i][j-1]; } fill_n(*dp,1001*1001,-INF); dp[0][0]=0; for(int i=1;i<N;i++){ int ma=-INF; for(int j=i;j>0;j--){ ma=max(ma,dp[i-1][j-1]); dp[i][j]=ma+sum(i,i-j,i-1)*2; } dp[i][0]=max(dp[i-1][0],ma); } cout<<*max_element(dp[N-1],dp[N-1]+1001)<<endl; return 0; }