JS's Blog
0%

Hdu 1078 - FatMouse and Cheese (基础dp)

Posted on Edited on In ,

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

题目大意：
有一只老鼠，起始点在(0,0)，起始获得一个权值，每次可以水平或垂直的至多走k步，获得该处的权值，且每次获得的权值必须比上一次的大，求最大能获得的总权值是多少

分析：
起点固定在(0,0),所以可以选dp[0][0]为dp终点，一开始以为是两点之间曼哈顿距离在k之内可达，后面一直WA，看了题解发现是题意读错了，只能上下或者左右走k步，所以结构体保存行列和权值信息，然后按权值从大到小，权值较大的先遍历，dp[i][j]表示以矩阵中(i,j)位置为起点能获得的最大权值和，dp转移式是

dp[i][j]=max⁡(max⁡p=j−kp≤j+k(dp[i][p]),max⁡q=i−kq≤i+k(dp[q][j]))+a[i][j]dp[i][j] = \max(\max_{p=j-k}^{p\leq j+k} (dp[i][p]),\max_{q=i-k}^{q\leq i+k}(dp[q][j]) )+a[i][j]

最后dp[0][0]dp[0][0]即是答案

代码：

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
68
69
70
71
72
73
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;
const int maxn = 1020000;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n,k;
int mat[120][120];
int dp[120][120];


struct Node{
    int v,r,c;
    bool operator < (const Node a)
    {
        return v>a.v;
    }
}arr[12000];


bool check(int i ,int j)
{
    if (i<1||i>n||j<1||j>n)
        return false;
    else
        return true;
}


int main()
{
    int t = 1 ;
    while (~scanf("%d%d",&n,&k))
    {
        if (n==-1&&k==-1)
            break;
        for (int i = 1;  i <= n ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                scanf("%d",&mat[i][j]);
                dp[i][j] = mat[i][j];
                arr[(i-1)*n+j].r = i;
                arr[(i-1)*n+j].c = j;
                arr[(i-1)*n+j].v = mat[i][j];

            }
        }
        sort(arr+1,arr+n*n+1);
        int x,y;
        for (int i = 1 ; i <= n*n ; i ++)
        {
            x = arr[i].r , y = arr[i].c;
            for (int p = -k ; p <= k ; p ++)
            {
                if (check(x+p,y)&&mat[x+p][y]>mat[x][y])
                    dp[x][y] = max(dp[x][y],dp[x+p][y]+mat[x][y]);
                if (check(x,y+p)&&mat[x][y+p]>mat[x][y])
                    dp[x][y] = max(dp[x][y],dp[x][y+p]+mat[x][y]);
            }
        }
        printf("%d\n",dp[1][1]);


    }

    return 0;
}