AcWing 1015. 摘花生(二维dp)

  • 时间:
  • 浏览:
  • 来源:互联网

题目
题意: 从[1][1]走到[r][c] 所能得到的最大花生数量。
关键:f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
f[i][j] 可能从当前位置的上或左到达,所以计算出两者的最大值即可

与01 dp 的区别是,01 只关心选或不选,而这个是从两个方位到达的。

答案:

#include<iostream>
#include<cstdio>
#include<algorithm>
 using namespace std;
  
 const int N=110;

int T,r,c,w[N][N],f[N][N];

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>r>>c;
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
				scanf("%d",&w[i][j]);
			}
		for(int i=1;i<=r;i++)
			for(int j=1;j<=c;j++)
			{
			 	f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j]; //f[i][j] 可能从当前位置的上或左到达,所以计算出两者的最大值即可 
			}
		cout<<f[r][c]<<endl;	 
	}
	return 0;
}

本文链接http://www.dzjqx.cn/news/show-617382.html