2016 UESTC Training for Dynamic Programming M-柱爺抢银行歓慶5.1 special递推

M-柱爺抢银行歓慶5.1 special
Time Limit: 1000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit  Status
柱爺が銀行を奪う手段は日増しに熟練している.5.1を祝うために、柱爺はもう花式で銀行を奪うつもりだ.
ニャーアサリ城は大きな矩形の方陣で、この方陣はN
aij<0柱爺は−aijのお金を失う.
柱爺は最近飛天螺旋の大草になったので、彼が奪う銀行はk k階の時計回りの螺旋状を形成することを決めた.そのうちkは≧3の任意の奇数である.次はk=3,5,7のパターンですが、
その中の黒いブロックは柱爺が金を奪う銀行だ.
すみません、柱爺は最大いくらまで奪うことができますか?
Input
最初の行の2つの数N,M.
その後、N N行毎にM個の数が、aijを表す.
データ保証:
3≤N,M≤500 .
−1000≤aij≤1000   .
Output
1行1つの数、すなわち答えを出力します.
Sample input and output
Sample Input
Sample Output

6 5
0 0 0 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1

17

3 3
1 1 1
1 0 0
1 1 1

6

6 6
-3 2 0 1 5 -1
4 -1 2 -3 0 1
-5 1 2 4 1 -2
0 -2 1 3 -1 2
3 1 4 -3 -2 0
-1 2 -1 3 1 2

13

Hint
柱爺は陣に臨んで引き下がる人ではないので、来た以上、少なくとも1つの格子を選んでください!(損をするかもしれないけど)
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)は、d 1−d 2−d 3+d 4の2次前置和から得ることができる.
複雑度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("");
    }
}

#include <iostream>
#include <cstdio>
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("
");
    }
    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;
}

Thank you!
                                                                                                                                               ------from  ProLights