Typical DP Contest L:猫

問題文

http://lattemalta.hatenablog.jp/entry/2015/09/21/014633

解法

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;
}