<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1015.摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。
地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数 $T$,代表一共有多少组数据。
接下来是 $T$ 组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数 $R$ 和列数 $C$
每组数据的接下来 $R$ 行数据,从北向南依次描述每行花生苗的情况
每行数据有 $C$ 个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目 $M$
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
$1 \le T \le 100$,
$1 \le R,C \le 100$,
$0 \le M \le 1000$
其实这道题我首先想的是记忆化搜索,但是发现更新顺序很像 DP,就用 DP 来切了
解法:DP 复杂度:$O(n ^ 2)$
状态表示
$f[i][j]$ 表示从左下角到位置 $[i, j]$ 的最大值
状态转移
很明显,枚举顺序是先行后纵
所以,$[i, j]$ (只能)依赖于 $[i - 1, j]$ 和 $[i, j - 1]$
也就是,f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w;
而第 i 层的答案只依赖于第 i 层和第 i - 1 层,容易想到滚动数组优化
在看到方程,发现不用滚动数组,直接用一维存即可(具体解释见代码)
一维转移:f[j] = max(f[j], f[j - 1]) + w;
答案表示
用二维存就是 f[n][m]
用一维存就是 f[m]
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
int T, n, m;
int f[N];
void solve()
{
cin >> n >> m;
fill(f + 1, f + m + 1, 0); //答案一定是非负整数,所以初始化所有 f[i] 为 0
for(int i = 1;i <= n;++ i) //枚举行
for(int j = 1, w;j <= m;++ j) //枚举列
{
cin >> w; //优化空间
f[j] = max(f[j], f[j - 1]) + w; //这里是优化,第 i 层只依赖于第 i 层和第 i - 1 层
//所以可以直接优化空间,这里的 f[j - 1] 对应的是 f[i][j - 1]
//而 f[j] 对应的是 f[i - 1][j]
}
cout << f[m] << endl; //f[m] 对应的是 f[n][m]
return;
}
int main()
{
cin >> T;//多行数据
while(T --) solve();
return 0;
}
大佬,用dfs()怎么写呀
感谢
请问你dfs写法ac了吗,为啥我tle了