POJ1088 滑雪題解+HDU 1078（記憶化搜尋DP)

Description

Michael喜歡滑雪百這并不奇怪， 因為滑雪的确很刺激。可是為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區域中最長底滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。下面是一個例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-…-3-2-1更長。事實上，這是最長的一條。

Input

輸入的第一行表示區域的行數R和列數C(1 <= R,C <= 100)。下面是R行，每行有C個整數，代表高度h，0<=h<=10000。

Output

輸出最長區域的長度。

Sample Input

5 5

1 2 3 4 5

Sample Output

25

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
#define mst(a,b)  memset((a),(b),sizeof(a));
const int max1=105;
long long int dp[max1][max1];
//int sum[max1];
long long int ob[max1][max1];
int dx[5]={0,-1,0,1,0},
    dy[5]={0,0,-1,0,1};
    //dx與dy一組，構成上下左右四個方向
long long int r,//長
            c,//寬
            t,//做中間變量，用來尋找最大的ans
            ans;//預設答案變量
int search(int x,int y);//聲明search函數
int main()
{
    cin>>r>>c;//輸入長寬
    ans=0;//無合适條件下設ans為最小值0
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>ob[i][j];//輸入矩陣
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){//周遊矩陣中每一個點
            t=search(i,j);//調用searc函數
            dp[i][j]=t;
            if(t>ans) ans=t;
        }
        cout<<ans<<endl;
}
int search(int x,int y)
{
    int w,tmp,nx,ny;
    if(dp[x][y]>0){ //如果dp大于0代表dp被調用過可以直接使用
        return(dp[x][y]);//傳回dp[i][j]的值
    }
    w=1;
    for(int i=1;i<=4;i++){//周遊四個方向
        nx=x+dx[i];
        ny=y+dy[i];
        if((nx>=1)&&(nx<=r)&&(ny>=1)&&(ny<=c)&&(ob[x][y]<ob[nx][ny])){//邊界
            tmp=search(nx,ny)+1;//遞歸求目前點能夠到達的最大值
            if(tmp>w) w=tmp;
        }
    }
        dp[x][y]=w;
        return w;
}
/*
5 5
1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
*/
           

FatMouse and Cheese

Problem Description

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse – after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k

n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) … (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), … (1,n-1), and so on.

The input ends with a pair of -1’s.

For each test case output in a line the single integer giving the number of blocks of cheese collected.

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int ob[10050][105];
int dp[10050][105];
int dx[4]={0,1,0,-1},
    dy[4]={1,0,-1,0};
int x,y,ans,temp,k;
int search(int q,int w);
int main()
{
    while(cin>>x>>k)
    {
        memset(ob,0,sizeof(ob));
        memset(dp,0,sizeof(dp));
        if(x==-1||y==-1) break;
        y=x;
        ans=0;
        for(int i=1;i<=y;i++)
            for(int t=1;t<=x;t++) cin>>ob[i][t];
            cout<<search(1,1)<<endl;
    }
}
int search(int q,int w)
{
    int nx,ny,t=0;
    if(dp[q][w]>0) return dp[q][w];
    for(int j=1;j<=k;j++)
    for(int i=0;i<4;i++)
    {
        nx=q+dx[i]*j;
        ny=w+dy[i]*j;
        if((nx>=1)&&(nx<=x)&&(ny>=1)&&(ny<=y)&&(ob[q][w]<ob[nx][ny]))
            t=max(t,search(nx,ny));
    }
    return dp[q][w]=t+ob[q][w];
}