首页 > 代码库 > XTU 1224 Endless Jump(dp)

XTU 1224 Endless Jump(dp)

2024-11-01 07:09:01   203人阅读

Endless Jump

Accepted : 10 Submit : 13
Time Limit : 5000 MS Memory Limit : 65536 KB

题目描述

在一个网格里面，每个格子有一个确定的高度，从一个格子上可以跳到相邻的格子上。 在里面的最左上角的格子上有一个程序猿刚刚打开电脑准备写程序， 但是他的键盘在最右下角的格子里面， 现在这个程序猿需要从最左上角跳到最右下角去拿到键盘后再跳回来。 但是他想尽量少的消耗自己的体力，因为他回来之后还要写一个月的程序。

从较高的格子上跳到较低的格子上不会消耗体力； 从较低的格子上跳到较高的格子上消耗的体力是两个格子高度之差。 因为键盘在最右下角，他去拿键盘的时候只会往右边或下边跳; 同理，拿了键盘回去的时候他只会往左边或上边跳。

输入

第一行是一个整数K(K大约100左右)，表示样例的个数。
每个样例第一行两个整数 n, m(2 ≤ n, m ≤ 1000)， 表示网格里面有n行每行m个格子；
之后有n行每行m个小于一万的非负整数，表示每个格子的高度；

输出

对于每个样例输出一个整数占一行，表示这个程序猿至少要消耗多少体力才能取回他的键盘。

样例输入

3
2 2
1 2
3 4
3 3
1 2 3
4 5 6
7 8 9
5 9
7 7 0 8 0 7 2 5 8
7 8 1 1 9 8 5 9 7
8 6 9 3 6 6 4 7 6
6 4 8 5 2 4 6 2 4
3 7 0 9 2 4 4 2 9

样例输出

3
8
24

提示

巨大的输入量，请使用C风格的输入避免超时。


Source

WW

类似数字三角形。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 100010
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lc idx<<1
#define rc idx<<1|1
const double EPS = 1e-11;
const double PI = acos ( -1.0 );
const double E = 2.718281828;
typedef long long ll;

const int INF = 1000010;

using namespace std;

int n,m;
int a[1010][1010],dp[1010][1010];

int main()
{
    int t;
    while(cin>>t)
    {
        while(t--)
        {
            scanf("%d%d",&n,&m);
            memset(a,0,sizeof a);
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            memset(dp,0,sizeof dp);
            for(int i=n; i>=1; i--)
            {
                for(int j=m; j>=1; j--)
                {
                    int flag=0;
                    if(i!=n)
                    {
                        flag=1;
                        if(a[i][j]<a[i+1][j])
                            dp[i][j]=dp[i+1][j]-a[i][j]+a[i+1][j];
                        else
                            dp[i][j]=dp[i+1][j];
                    }
                    if(j!=m)
                    {
                        if(flag)
                        {
                            if(a[i][j]<a[i][j+1])
                                dp[i][j]=min(dp[i][j],dp[i][j+1]-a[i][j]+a[i][j+1]);
                            else
                                dp[i][j]=min(dp[i][j],dp[i][j+1]);
                        }
                        else
                        {
                            if(a[i][j]<a[i][j+1])
                                dp[i][j]=dp[i][j+1]-a[i][j]+a[i][j+1];
                            else
                                dp[i][j]=dp[i][j+1];
                        }
                    }
                }
            }
            int ans=dp[1][1];
            memset(dp,0,sizeof dp);
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=m; j++)
                {
                    int flag=0;
                    if(i!=1)
                    {
                        flag=1;
                        if(a[i][j]<a[i-1][j])
                            dp[i][j]=dp[i-1][j]-a[i][j]+a[i-1][j];
                        else
                            dp[i][j]=dp[i-1][j];
                    }
                    if(j!=1)
                    {
                        if(flag)
                        {
                            if(a[i][j]<a[i][j-1])
                                dp[i][j]=min(dp[i][j],dp[i][j-1]-a[i][j]+a[i][j-1]);
                            else
                                dp[i][j]=min(dp[i][j],dp[i][j-1]);
                        }
                        else
                        {
                            if(a[i][j]<a[i][j-1])
                                dp[i][j]=dp[i][j-1]-a[i][j]+a[i][j-1];
                            else
                                dp[i][j]=dp[i][j-1];
                        }
                    }
                }
            }
            ans+=dp[n][m];
            cout<<ans<<endl;
        }
    }
    return 0;
}


XTU 1224 Endless Jump(dp)


联系
我们