lightoj 1071 - Baker Vai

发表于   |   分类于   |     |   阅读次数

摘要:记忆化搜索

正文:
All of you must have heard the name of Baker Vai. Yes, he rides a bike and likes to help people. That’s why he is popular amongst general people.

Baker Vai lives in a city which can be modeled as a 2D m x n matrix. Where the north-west corner is cell 1, 1 and the south-east corner is cell m, n. In each cell there are certain amount of people who needs help which is already known to Baker Vai.

Each day Baker Vai starts his journey from the north-west corner and he can only go to east or south. This way he reaches the south-east corner of the city. After that he returns back to the north-west, but this time he can only move to west or north. He doesn’t want a cell to be visited twice other than the two corners. And if he visits a cell, he helps all the people in the cell.

Now you are given the map of the city and the number of people who need help in all cells for a particular day. You have to help Baker Vai finding the maximum number of people he can help in that day.

Input
Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case contains a blank line and two integers, m, n (2 ≤ m, n ≤ 100). Each of the next m lines will contain n integers, denoting the number of people who are in need. In a cell there will be no more than 20 people and a cell can be empty, too.

Output
For each test case, print the case number and the maximum number of people Baker Vai can help considering the above conditions.

Sample Input

2

3 3
1 1 1
1 0 1
1 1 1

3 4
1 1 0 1
1 1 1 1
0 1 10 1

Output for Sample Input

Case 1: 8
Case 2: 18

在一个n*m方格里，两个机器人同时从左上角(1,1)走到右下角(n,m)，除了起点和终点可以同在一个方格，过程中不允许两个机器人在同一个地方，并且机器人每次只能向右或向下行动。每个机器人走路的花费等于它走的过程中方格数字的和，(1,1),(n,m)处数字只算一次，问最小的花费。

寒假做过一次，cfdiv2里e难度，然后我没补…遭报应了。
首先表示状态，dp[step][x1][y1][x2][y2],就是机器人走了step次，第一个机器人在(x1,y1)处，第二个在(x2,y2)处所走的最小花费，这个状态表示肯定不行，然后发现x1 + y1 = step + 2，那么只用x1，x2，step就可以把整个状态表示出来了，剩下的就是记忆化搜索了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<utility>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int n,m;
int a[105][105];
int dp[220][105][105];
int dir[4][2] = {0,0,1,0,0,1,1,1};
int dfs(int step,int x,int y){
    //cout<<step<<" "<<x<<" "<<y<<endl<<endl;l
    if(x > n || y > n)return -inf;
    if(2 + step - x > m)return -inf;
    if(2 + step - y > m)return -inf;
    if(step == n + m - 2){
        if(x == n && y == n)return dp[step][x][y] = a[n][m];
        return dp[step][x][y] = -inf;
    }
    if(x == y && step != 0)return dp[step][x][y] = -inf;
    int &ans = dp[step][x][y];
    if(ans != -1)return ans;
    for(int i = 0;i < 4;i++){
        int tempx = x + dir[i][0];
        int tempy = y + dir[i][1];
        //if(tempx > n || tempy > n)continue;
        //if(step - tempx + 2 > m)continue;
        //if(step - tempy + 2 > m)continue;
        ans = max(ans,dfs(step + 1,tempx,tempy));
    }
    if(ans == -1)
        return ans = -inf;
    if(step == 0)
        return ans;
    return ans = ans + a[x][step - x + 2] + a[y][step - y + 2];
}
int main()
{
	#ifdef LOCAL
	freopen("C:\\Users\\ΡΡ\\Desktop\\in.txt","r",stdin);
	//freopen("C:\\Users\\ΡΡ\\Desktop\\out.txt","w",stdout);
	#endif // LOCAL
	int t,kase = 1;
	scanf("%d",&t);
	while(t--){
        scanf("%d%d",&n,&m);
        memset(dp,-1,sizeof(dp));
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
            scanf("%d",&a[i][j]);
        printf("Case %d: %d\n",kase++,dfs(0,1,1) + a[1][1]);
	}
	return 0;
}