Grid-dp，交互

P14000 Grid-dp,交互

P14000 Grid

题意

给定一个 \(N*M\) 的矩阵，从 0,0 开始，每次只能向一个方向移动任意格，每次移动会得到 (令 \(x\) 为当前值， \(y\) 为转移) \(\left| a_x - a_y\right| -c\) ， 所以 $ dp_x = dp_y +\left|a_x - a_y\right| -c$,如果当前值更大，我们希望 \(dp_y-a_y\) 最小，同理，如果当前值更小，我们希望 \(dp_y+a_y\) 最大。

code + greader

// code
#ifndef ONLINE_JUDGE
#include "grid.h"
#endif // ONLINE_JUDGE#include <bits/stdc++.h>
#define ll long long
using namespace std;constexpr ll INF = 0x3f3f3f3f3f3f3f3f;// 令x为当前值，y为转移
// dp_x = dp_y + |a_x - a_y| -c
// 如果当前值更大，我们希望 dp_y-a_y 最小，此时+x
// 同理，如果当前值更小，我们希望dp_y+a_y最大，此时-x
// 令ma1为dp_y+a_ylong long max_profit(int n, int m, int c, std::vector<std::vector<int>> a)
{vector<vector<ll>> dp(n,vector<ll>(m,-INF));vector<ll> ma1_r(n,-INF) ,ma2_r(n,-INF);vector<ll> ma1_c(m,-INF) ,ma2_c(m,-INF);dp[0][0]=0;ma1_r[0]=a[0][0];  // 第0行 + 的最大值ma2_r[0]=-a[0][0]; // - 的最大值ma1_c[0]=a[0][0];ma2_c[0]=-a[0][0];for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(!i && !j) continue;int x=a[i][j];ll rm=max(ma1_r[i]-x,ma2_r[i]+x)-c;ll cm=max(ma1_c[j]-x,ma2_c[j]+x)-c;dp[i][j]=max(rm,cm);ma1_r[i]=max(ma1_r[i],dp[i][j]+x);ma2_r[i]=max(ma2_r[i],dp[i][j]-x);ma1_c[j]=max(ma1_c[j],dp[i][j]+x);ma2_c[j]=max(ma2_c[j],dp[i][j]-x);}}return dp[n-1][m-1];
}

code + greader

// greader
#include "grid.h"
#include<iostream>
#include<vector>
using namespace std;
int main ()
{freopen("sample.in","r",stdin);// 本地测试freopen("sample.out","w",stdout);int n, m, c;cin >> n >> m >> c;vector<vector<int>> inp(n, vector<int>(m));for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){cin >> inp[i][j];}}long long ans = max_profit(n, m, c, inp);cout << ans << endl;return 0;
}

//grid.h
#include <vector>long long max_profit(int N, int M, int C, std::vector<std::vector<int>> A);