NYOJ-104最大和
2024-10-13 00:56:50
我看了好多博客,都是拿一维的做基础,一维的比较简单,所以要把二维的化成一维的,一维的题目大意:给了一个序列,求那个子序列的和最大,这时候就可以用dp来做,首先dp[i]表示第i个数能构成的最大子序列和,所以dp[i] = dp[i - 1] > 0 ? dp[i - 1] + dp[i] : dp[i]; 这个比较好理解,但是二维的,貌似想不起来这样写了。但是,如果转换一下,还是可以的,方法如下:
1. 将行划分,划分的结果为所有情况
2.将划分好的“新行”进行合并成“一行”,
3.对“一行”进行一维的求最大子段和
举个例子:
0 -2 -7 0
9 2 -6 2
-4 1 -4 7
-1 8 0 -2
我们分别用i j表示起始行和终止行,遍历所有的可能:
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {}
我们考察其中一种情况 i=2 j=4,这样就相当与选中了2 3 4三行,求那几列的组合能获得最大值,由于总是 2 3 4行,所以我们可以将这3行”捆绑”起来,变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)的最大子段和,ok,问题成功转化为一维的情况!
注意:代码中还有一个地方需要注意,就是读入原始数据的时候,要处理一下,再保存到数组中,每一行的数据都不是原来的数据,而是加上同一列以上各行的数据,这样以来,在合并求和的时候就比较方便了。比如求2,3两行的和,只要第三行的值减去第一行的值就行了
代码如下:
#include<iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 99999999
using namespace std;
const int n = ;
int map[n][n];
int temp[n];
int ans;
//一维序列求最大和
int find_max(int a[], int m)
{
int max_sum = -inf;
int res = ;
for (int k = ; k <= m; k++)
{
if (res > )
res += a[k];
else
res = a[k];
if (res > max_sum)
max_sum = res;
}
return max_sum;
}
int main()
{
int n;
cin >> n;
while (n--)
{
memset(map, , sizeof(map));
int r, c;
int t;
cin >> r >> c;
for (int i = ; i <= r; i++)
{
for (int j = ; j <= c; j++)
{
cin >> map[i][j];
map[i][j] += map[i - ][j];//处理一下
}
}
ans = -inf;
for (int i = ; i < r; i++)
{
for (int j = i + ; j <= r; j++)//枚举所有情况
{
for (int k = ; k <= c; k++)//将“新和”计算出来保存到数组temp中
{
temp[k] = map[j][k] - map[i][k];
}
//找到这段当中的最大和
t = find_max(temp, c);
if (t > ans)
ans = t;//ans全局变量保存结果,即最大值
}
}
cout << ans << endl;
} return ;
}
最新文章
- c#DataGridView数据绑定示例——格式化单元格的内容(转)
- Tomcat安装配置
- SQL Server 数据库的维护(一)__存储过程(procedure)
- 如何在MAC上使用SVN,简单几行命令搞定
- eclipse智能提示
- Oracle 常用入侵命令
- 图的最短路算法 Bellman-Ford
- SQL Service Database BACKUP &; RESTORE
- Monkey源码分析之事件注入
- C++中printf和scanf的用法
- [20190419]shared latch spin count.txt
- c++面经积累<;2>;
- VBA在WORD应用中如何将格式应用于选定内容
- 代码: 两列图片瀑布流(一次后台取数据,图片懒加载。下拉后分批显示图片。图片高度未知,当图片onload后才显示容器)
- 用python做网页抓取与解析入门笔记[zz]
- nodejs文件操作笔记
- 读着读着《构建之法》(Build To Win) 越精神的白雪儿的思考
- [CF19B]Checkout Assistant
- IntelliJ IDEA java开发 WebService
- 说说API的重放机制