摘花生 刷题笔记

index.php/tags-41973.html" >���路 dp

开一个 f[N][N]数组

f[i][j]表示 当走到位置i,j时 所摘到的花生的最大值 

对于任意一个位置i,j

因为只能向东或者向南走

所以 当前花生最大值只能来自左边或者上面

第i,j号位置的花生数 已经确定

所以只需取左边和上面的花生数的最大值即可

即f[i][j]=max（f[i-1][j],f[i][j-1])+w[i][j];

f[i-1][j]就是当前位置的左边花生数

f[i][j-1]则是上面的花生数 

因为每一次的选择都是基于左边和上边取得最大值

所以总体最大

代码

#include

#include

#include

#include

using namespace std;

const int N=110;

int w[N][N],f[N][N];

int main(){

    int n;

    cin>>n;

    while(n--){

        int r,c;

        cin>>r>>c;

        for(int i=1;iw[i][j];

                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];

            }

        }

        cout