HDU2391(简单dp)

题目链接

传送门

题目大意

题目大意就是给你一个n * m的矩阵,问你每次只能走右、下、右下这三个方向,从坐上出发到达右下,每个格子有相应的金币数,问最多能得到多少金币。

解题思路

根据dp的思想,对任意一个状态,我可以推导它的前一个状态。对于本题来说,我们还可以进一步优化,因为规定每个格子的金币数为正数,所以当你选择直接走右下这个策略并不是最优的,我们不妨走两个格子到达右下,总比一个格子要好得多(没准多走的那个格子有金币呢)。
状态转移方程dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
最后注意每组样例结束后都要有一个空行,不然报PE。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <complex>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
using namespace std;  

#pragma comment(linker, "/STACK:102400000,102400000")  

typedef long long LL;  
typedef double DB;  
typedef unsigned uint;  
typedef unsigned long long uLL;  

/** Constant List .. **/ //{  

const int MOD = int(1e9)+7;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;  
const DB EPS = 1e-9;  
const DB OO = 1e20;  
const DB PI = acos(-1.0); //M_PI;  
int maps[1111][1111];  
int dp[1111][1111];  

int n , m;  

int main()  
{  
    #ifdef DoubleQ  
    freopen("in.txt","r",stdin);  
    #endif  
    int T;  
    scanf("%d",&T);  
    int cas = 1;  
    while(T--)  
    {  
        scanf("%d%d",&n,&m);  
        for(int i = 0 ; i < n ; i ++)  
        {  
            for(int j = 0 ; j < m ; j ++)  
                scanf("%d",&maps[i][j]);  
        }  
        int ans = 0;  
        for(int i = 0 ; i < n ; i ++)  
        {  
            for(int j = 0 ; j < m ; j ++)  
            {  
                maps[i][j] += max(maps[i-1][j],maps[i][j-1]);  
            }  
        }  
        printf("Scenario #%d:\n%d\n\n",cas++ , maps[n-1][m-1]);  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图