本文主要是介绍nyoj234 吃土豆 dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本题的题意是 给一个矩阵map[m][n]充满了具有质量的豆子,每个位置限一个,现在让你吃掉尽可能质量大的豆子。限制条件是如果吃了map[i][j]的豆子,该位置的上下行和左右列的豆子就无法吃到。
思路:先求出每行能吃到的豆子的最大质量,然后对比各行求出矩阵内能吃到的最大质量的豆子。
#include <bits/stdc++.h>
#define maxn 510
using namespace std;
int Map[maxn][maxn];
int dp[maxn];
int main(){int m,n;while(cin>>m>>n){memset(Map,0,sizeof(Map));memset(dp,0,sizeof(dp));int d;for(int i=3;i<=m+2;i++){//防止越界for(int j=3;j<=n+2;j++){cin>>d;Map[i][j]=max(Map[i][j-2],Map[i][j-3])+d;}}int maxx=-maxn;for(int i=3;i<=m+2;i++){dp[i]=max(dp[i-2],dp[i-3])+max(Map[i][n+2],Map[i][n+1]);maxx=max(maxx,dp[i]);}cout<<maxx<<endl;}
}
这篇关于nyoj234 吃土豆 dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!