题目描述
萃香是一个极其喜欢喝⑨酒的鬼，有着操控密度的能力。
某天，在博丽神社举行的夏日大宴会上，萃香被灵梦请去玩一个游戏。
萃香需要操控一个在n行m列的方格的左上角 $_math_inline$(1,1)$math_inline_$ 的气团，让这个气团最后行进到右下角 $_math_inline$(n,m)$math_inline_$ 。萃香可以在每一格控制这个气团的密度。由于一些黑幕神奇的原因，可以认为这个气团的密度只有“高”和“低”两种，并且气团只能向右或向下移动。这个方格也不是一个什么一般的方格。在这里面，荷取受灵梦的请求，安装了一些奇特的装置。具体地说，对于 $_math_inline$(i,j)$math_inline_$ ，都有一个对应的权值 $_math_inline$V_{i,j}$math_inline_$ 。
- 若 $_math_inline$V_i,j=0$math_inline_$ ，那么气团进入这个格子的时候对密度没有要求。
- 若 $_math_inline$V_i,j=1$math_inline_$ ，那么气团进入这个格子的时候的密度必须是"低"。
- 若 $_math_inline$V_i,j=2$math_inline_$ ，那么气团进入这个格子的时候的密度必须是"高"。
注意：如果气团所在的格子 $_math_inline$V_i,j=1$math_inline_$ ，气团的密度可以变成"高"，反之亦然。记气团以“高”密度和“低”密度分别移动了 $_math_inline$a,b$math_inline_$ 次，那么萃香最后的得分就是a与b的差值的绝对值，即 $_math_inline$|a−b|$math_inline_$ 。灵梦和萃香提前做了一个约定，如果萃香获得了 $_math_inline$x$math_inline_$ 分，那么灵梦就要给她装满了 $_math_inline$x$math_inline_$ 个葫芦的酒。由于灵梦还没有买好酒，你需要帮灵梦求出萃香最多可以得到多少葫芦的酒。
输入
第一行两个整数n,m。
接下来n行，每行m个整数代表 $_math_inline$V_{i,j}$math_inline_$ 。
输出
一个整数代表萃香最多可以得到多少葫芦的酒。
样例输入
13 3
20 0 0
30 1 1
40 1 2
样例输出
12
提示： 对于100%的数据，n,m≤5000
根据题意，每一格的气团密度是由上一格决定的，那么就可以使用DP来解决
Code
1/**
2 * author: Akvicor
3 * created: 2019-07-15 12-55-15
4**/
5
6#include <bits/stdc++.h>
7
8using namespace std;
9
10#ifdef DEBUG
11string to_string(string s) {
12 return '"' + s + '"';
13}
14
15string to_string(const char* s) {
16 return to_string((string) s);
17}
18
19string to_string(bool b) {
20return (b ? "true" : "false");
21}
22
23template <typename A, typename B>
24string to_string(pair<A, B> p) {
25 return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
26}
27
28template <typename A>
29string to_string(A v) {
30 bool first = true;
31 string res = "{";
32 for (const auto &x : v) {
33 if (!first) {
34 res += ", ";
35 }
36 first = false;
37 res += to_string(x);
38 }
39 res += "}";
40 return res;
41}
42
43void debug_out() { cerr << endl; }
44
45template <typename Head, typename... Tail>
46void debug_out(Head H, Tail... T) {
47 cerr << " " << to_string(H);
48 debug_out(T...);
49}
50#endif
51
52#ifdef DEBUG
53#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
54#else
55#define debug(...) 17
56#endif
57
58#ifdef DEBUG
59#define FAST_IO 17
60#else
61#define FAST_IO std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0)
62#define endl '\n'
63#endif
64
65#define LL long long
66#define ULL unsigned long long
67#define rep(i, n) for(int i = 0; i < (n); ++i)
68#define reep(i, n) for(int i = 0; i <= (n); ++i)
69#define lop(i, a, n) for(int i = a; i < (n); ++i)
70#define loop(i, a, n) for(int i = a; i <= (n); ++i)
71#define ALL(v) (v).begin(), (v).end()
72#define PB push_back
73#define VI vector<int>
74#define PII pair<int,int>
75#define FI first
76#define SE second
77#define SZ(x) ((int)(x).size())
78
79const double EPS = 1e-6;
80const double PI = acos(-1.0);
81const int INF = 0x3f3f3f3f;
82const LL LINF = 0x7f7f7f7f7f7f7f7f;
83const int MAXN = (int)1e6 + 10;
84const int MOD = (int)1e9 + 7;
85
86int v[5010][5010], n, m, dp[2][5010][5010];
87
88int main(){
89
90 FAST_IO;
91
92 cin >> n >> m;
93
94 loop(i, 1, n) loop(j, 1, m) cin >> v[i][j];
95
96 loop(i, 1, n)
97 loop(j, 1, m){
98 if(i==j && i==1) continue;
99 if(v[i][j] == 0){
100 dp[0][i][j] = max(dp[0][i-1][j], dp[0][i][j-1]) + 1;
101 dp[1][i][j] = max(dp[1][i-1][j], dp[1][i][j-1]) + 1;
102 }else if(v[i][j] == 1){
103 dp[0][i][j] = max(dp[0][i-1][j], dp[0][i][j-1]) + 1;
104 dp[1][i][j] = max(dp[1][i-1][j], dp[1][i][j-1]) - 1;
105 }else if(v[i][j] == 2){
106 dp[0][i][j] = max(dp[0][i-1][j], dp[0][i][j-1]) - 1;
107 dp[1][i][j] = max(dp[1][i-1][j], dp[1][i][j-1]) + 1;
108 }
109 }
110
111 cout << max(dp[0][n][m], dp[1][n][m]) << endl;
112 return 0;
113}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。