首页 > 代码库 > hdu2845（dp）

hdu2845（dp）

2024-08-10 14:22:24   220人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2845

题意：给你一个n*m的矩阵，每个位置有一定数量的豆子，如果你去map[x][y]位置上的豆子，则map[i-1][]行和map[i+1][]行，以及map[i][j-1]和map[i][j+1]位置上的豆子都不能再取。

分析：水dp，先算出每行的最大值，在对n行的最大值dp得结果。dp[i][1]表示前i个且取了第i个达到的最大值，dp[i][0]表示前i个且不取第i个达到的最大值。

状态转移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+b[i];

技术分享
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 200010using namespace std;int a[N];int mx[N],dp[N][2];int n,m;int solve(int b[],int sum){    for(int i=1; i<=sum; i++)    {        dp[i][1]=dp[i-1][0]+b[i];        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);    }    return max(dp[sum][0],dp[sum][1]);}int main(){    while(scanf("%d%d",&n,&m)>0)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=m; j++)            {                scanf("%d",&a[j]);            }            mx[i]=solve(a,m);        }        int ans=solve(mx,n);        printf("%d\n",ans);    }}
View Code

 

hdu2845（dp）


联系
我们