【dp】POJ-1050

淩亂°似流年 2021-12-05 13:09 220阅读 0赞

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大.  
首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。  
因为是连续若干个自然数的和，那前面的某个数字取与不取的条件在于：以前面这个数字为结尾的连续数的和最大值是否大于0。如果大于0，那么这个数字必然要会出现在包括数字的序列中，否则无法做到最大。  
处理的原则是maxn\[i\]=max\{0,maxn\[i-1\]\}+a\[i\];

现在再来看看多列数字，我们可以将多列数字转换成单列数字来做！ 可以这样设想，结果是一个长方形，我们把他压扁，使得宽为1。

引入辅助数组st,st\[i\]\[j\]代表第i列从第1行开始的数字累加到第j行的值。那么，我们每次压扁的时候，就可以用st\[i\]\[j\]-st\[i\]\[k-1\]来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。算法时间复杂度O (N^3)。

\#include "stdio.h"

\#include "string.h"

\#define N 101

int f\[N\]\[N\];

int v\[N\]\[N\];

int main()

\{

int n , i , j , k , max\_sub , sum , curr\_max;

scanf("%d",&n);

for( i = 0 ; i < n ; i++ )

for( j = 0 ; j < n ; j++ )

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

memset(f,0,sizeof(f));

max\_sub = 0;

for( i = 0 ; i < n ; i++ )

\{

for( j = i+1 ; j < n+1 ; j++ )

\{

curr\_max = 0 ;

sum = 0 ;

for( k = 0 ; k < n ; k++ )

\{

f\[k\]\[j\] = f\[k\]\[j-1\] + v\[k\]\[j-1\];

sum += f\[k\]\[j\] - f\[k\]\[i\]; //相当于找一列的最大值

if(sum < 0)

sum = 0;

if(sum > curr\_max)

curr\_max = sum;

\}

if(curr\_max > max\_sub)

max\_sub = curr\_max;

\}

\}

printf("%d\\n",max\_sub);

return 0;

\}

另外一个code:

\#include <stdio.h>

\#include <stdlib.h>

\#include <string.h>

void main()\{

int a\[105\]\[105\];

int b\[105\];

int i,j,p,q,max=-9999,num,k;

scanf("%d",&num);

for(i=1;i<=num;i++)

for(j=1;j<=num;j++)

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

for(i=1;i<=num;i++)

for(j=i;j<=num;j++)

\{

memset(b,0,sizeof(b));

for(p=1;p<=num;p++)

for(q=i;q<=j;q++)

b\[p\]+=a\[q\]\[p\];       //记录了一列中i到j的值

for(k=1;k<=num;k++)

if(b\[k\]>0)

b\[k+1\]+=b\[k\];

for(k=1;k<=num;k++)

if(b\[k\]>max)

max=b\[k\];

\}

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

\}

转载于:https://www.cnblogs.com/zuckerTT/archive/2011/09/25/2189856.html

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关 dpPOJ 2027 LCIS（最长上升公共子序列）

题意和解析见代码最后部分 include<iostream> include <cstdio> include <cstring>

我不是女神ヾ/ 2022年08月18日 00:48/ 0 赞/ 116 阅读

相关 poj1050 to the Max

\include <stdio.h> \include <string.h> \define N 103 int fun(int b\[N\

快来打我*/ 2022年06月18日 11:51/ 0 赞/ 101 阅读

相关 1050. String Subtraction (20)

Given two strings S1 and S2, S = S1 \- S2 is defined to be the remaining string after ta

待我称王封你为后i/ 2022年05月31日 12:08/ 0 赞/ 88 阅读

相关 1050. 螺旋矩阵(25)

本题要求将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第1个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为m行n列，满足条件：m\n等于N

男娘i/ 2022年05月26日 07:38/ 0 赞/ 121 阅读

相关 HDU-1050-Moving Tables

Moving Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (

我不是女神ヾ/ 2022年05月20日 04:55/ 0 赞/ 89 阅读

相关 1050 螺旋矩阵（25 分）

本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条

朱雀/ 2022年05月15日 16:55/ 0 赞/ 141 阅读

相关 HDU-1050——Moving Tables

Moving Tables Problem Description The

Love The Way You Lie/ 2022年04月11日 13:53/ 0 赞/ 93 阅读

相关 POJ1050 To the Max

题目链接：[contest-hunter.org:83/contest/0x08「基本算法」练习/POJ1050][contest-hunter.org_83_contest_

冷不防/ 2022年01月13日 10:07/ 0 赞/ 144 阅读

相关【dp】POJ-1050

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大. 首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。因为是连续若干个自然数的和，那前面的某个数字取

淩亂°似流年/ 2021年12月05日 13:09/ 0 赞/ 221 阅读

相关 hdu 1050

这题思路百度的，自己的思路太差了，不行，百度到的思路非常巧妙，哪一段重合的次数最大就是要移动的时间\10...orz神牛们.. ![ContractedBlock.gif][

川长思鸟来/ 2021年10月23日 12:12/ 0 赞/ 180 阅读