hdu1081

1678 단어
1차원 최대 필드 및
int dp(int n)
{
    int i, j, sum = 0, max = -10000;
    for(i = 1; i <= n; i++)
    {
        if(sum < 0)
            sum = 0;
        sum += a[i];
        if(sum > max)
            max = sum;
    }
    return sum;
}

k행 i-j열의 최대 자단과 왜 1부터 꺼내야 하는지, dp의 초기화에 주의하십시오.
현재 k-1 줄의sum<0 시, 현재의sum에 추가하면 현재의sum를 더욱 작게 만들 수 있습니다
for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                for(int k=1,sum=0;k<=n;k++)
                {
                    sum=sum>0?sum:0;
                    sum=sum+dp[k][j]-dp[k][i-1];
                    if(m<sum)m=sum;
                }
            }
        }
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
    //freopen("in.txt","r",stdin);
    int dp[102][102],a,n;

   while( scanf("%d",&n)!=EOF)
   {

        int m=-0xfffffff;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a);
                dp[i][j]=dp[i][j-1]+a;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                for(int k=1,sum=0;k<=n;k++)
                {
                    sum=sum>0?sum:0;
                    sum=sum+dp[k][j]-dp[k][i-1];
                    if(m<sum)m=sum;
                }
            }
        }
        printf("%d
",m); } return 0; }

좋은 웹페이지 즐겨찾기