poj 1050 To the Max (简单dp)

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn = ;

const int INF = 0x3f3f3f;

int dp[maxn];

int sum[maxn][maxn];

int ans;

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int N;

    cin>>N;

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

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

        for(int j=;j<=N;j++){

            int a;

            scanf("%d",&a);

            sum[i][j] = sum[i-][j] + a;

    }

    ans = -INF;

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

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

            memset(dp,,sizeof(dp));

            for(int k=;k<=N;k++){

                dp[k] = max(,dp[k-]) + sum[j][k] - sum[i][k];

                ans = max(dp[k],ans);

            }

    }

    printf("%d\n",ans);

}

//自己的做时候，一直想怎样写dp并表示出状态转移方程，但是就是怎么也想不出来，觉得不好表示。没办法看了别人的想法，马上反应过来。头脑僵化了啊！！！
秒客网

poj 1050 To the Max (简单dp)

相关文章
