2016 UESTC Training for Dynamic Programming M – 柱爷抢银行欢庆5.1special 递推

Source

2016 UESTC Training for Dynamic Programming

My Solution

递推

k阶的图刚好是k+2阶的图的白色部分 - val[i][j];

所以刚好dp[i][j] = getsum(i, j, i+k-1, j+k-1) - dp[i+1][j+1] - val[i+1][j];

//dp[i+1][j+1] 还是上一个k 的

其中getsum(i, j, i+k-1, j+k-1)可以从二阶前置和得到， d1 - d2 - d3 + d4;

复杂度 O(n^3)

第一次碰到二阶前缀和，随便贴一个我写的版嘿嘿

inline int getsum(int i, int j, int x, int y)

{

return (sum[x][y] - sum[x][j-1] - sum[i-1][y] + sum[i-1][j-1]);

}

void read()

{

for(int i = 0; i <= M; i++) sum[0][i] = 0;

for(int i = 1; i <= N; i++){

s[0] = 0;//这个可以直接放外面

for(int j = 1; j <= M; j++){

scanf("%d", &val[i][j]);

dp[i][j] = val[i][j];

//预处理二阶前缀和

s[j] = s[j-1] + val[i][j];

sum[i][j] = sum[i-1][j] + s[j-1] + val[i][j];

//printf("sum[%d][%d] = %d;", i, j, sum[i][j]);

}

//printf("n");

}

}

#include 
#include 
using namespace std;
const int maxn = 500 + 8;
int val[maxn][maxn], dp[maxn][maxn], sum[maxn][maxn], s[maxn];

inline int getsum(int i, int j, int x, int y)
{
    return (sum[x][y] - sum[x][j-1] - sum[i-1][y] + sum[i-1][j-1]);
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int N, M, K;
    scanf("%d%d", &N, &M);

    for(int i = 0; i <= M; i++) sum[0][i] = 0;
    for(int i = 1; i <= N; i++){
        s[0] = 0;//这个可以直接放外面
        for(int j = 1; j <= M; j++){
            scanf("%d", &val[i][j]);

            dp[i][j] = val[i][j];
            //预处理二阶前缀和
            s[j] = s[j-1] + val[i][j];
            sum[i][j] = sum[i-1][j] + s[j-1] + val[i][j];
            //printf("sum[%d][%d] = %d;", i, j, sum[i][j]);
        }
        //printf("n");
    }
    K = min(N, M);
    int ans = -7*1002; //如果全负数就选3阶了，最多7个 -1000
    //k = 1 的时候 dp[i][j] 就是 val[i][j] 了 上面已经处理好了
    for(int k = 3; k <= K; k += 2){
        for(int i = 1; i + k - 1 <= N; i++){
            for(int j = 1; j + k - 1 <= M; j++){
                dp[i][j] = getsum(i, j, i+k-1, j+k-1) - dp[i+1][j+1] - val[i+1][j];  //dp[i+1][j+1] 还是上一个k 的
                //cout<<dp[i][j]<<endl;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx