题目链接

1015. 摘花生 - AcWing题库

数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！

一些话

我也不懂什么叫线性dp，和其他dp不知道有什么区别，做的题太少了。

写博客主要是记录下闫氏dp分析法

切入点

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

hk的走法有很多，属于最优解问题，符合dp特征

1≤T≤100
1≤R,C≤100

最多1e2*3,完全够时间，可以dp

流程

// f[i][j]，走法的集合，走到i，j的走法
// 属性是maxn

// 集合划分，最后一个不同的点，f[i][j]可以由上得也可由左得，
// 上：f[i-1][j] + w[i][j]，左：f[i][j-1] + w[i][j];
// 取二者最大

套路

闫氏dp

ac代码

// f[i][j]，走法的集合，走到i，j的走法// 属性是所有走法的最大花生// 集合划分，最后一个不同的点，f[i][j]可以由上得也可由左得，取二者最大
#include 
#include 
#include 
#include 
using namespace std;
const int N = 110;
int f[N][N],w[N][N];
int  main(){int t;cin >> t;while(t--){int n,m;cin >> n >> m;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> w[i][j];}}for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){f[i][j] = max(f[i-1][j],f[i][j-1]) + w[i][j];}}cout << f[n][m] << endl;}}

我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！我草，又~在～水～字～数～啦！

上一篇：锂电池正极材料离心母液回收镍钴技术

下一篇：pyflink学习笔记(六)：窗口函数

闫氏dp分析法（线性dp）AcWing 1015. 摘花生

目录

题目链接

一些话

切入点

流程

套路

ac代码

相关内容

热门资讯