AcWing 1015. 摘花生-附最小值情况的分析
原题链接
简单
作者:
Nova_Lciop
,
2023-12-12 10:37:11
,
所有人可见
,
阅读 46
//附最小值情况的分析
#include<bits/stdc++.h>
using namespace std;
const int modsize=1005;
int R[modsize],C[modsize];
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)
{
int M[modsize][modsize],dp[modsize][modsize];
cin>>R[i]>>C[i];
for(int j=1;j<=R[i];j++)
{
for(int k=1;k<=C[i];k++)
{
cin>>M[j][k];
}
}
//dp[1][1]=M[1][1]; //初始化dp[1][1]
//dp[1][1]=M[1][1];
//dp[1][2]=dp[1][1]+M[1][2];
//dp[2][1]=dp[1][1]+M[2][1];
//dp[1][3]=dp[1][2]+M[1][3];
//cout<<dp[1][1]<<' '<<dp[1][2]<<' '<<dp[2][1]<<' ';
for(int j=1;j<=R[i];j++)
{
for(int k=1;k<=C[i];k++)
{
if(j!=1&&k!=1)
dp[j][k]=max(dp[j-1][k],dp[j][k-1])+M[j][k]; //题意为求最大值
//dp[j][k]=min(dp[j-1][k],dp[j][k-1])+M[j][k]; //若求最小值
else if(j==1) dp[j][k]=dp[j][k-1]+M[j][k];
else if(k==1) dp[j][k]=dp[j-1][k]+M[j][k];
}//我们可以大致像y总一样画一个状态思维分析图,很多题解其实是不适合求最小值情况的
//因此我们可以分段进行讨论,主要是关于j==1和k==1两种情况分开讨论,按照正常做
//最大值的时候我们不太需要考虑数组下标为0的情况(因为dp(j,0),dp(0,k)一定为0)即不需要考虑
//max的情况,而最小值则需要考虑.
}
cout<<dp[R[i]][C[i]]<<'\n';
}
return 0;
}