題目：
? 有n座山峰，每個山峰都有自己的高度和值，現在出題人要在群山中穿梭，穿梭有兩個條件：1 他們只會去高度大于當前所在山峰的高度的山峰；2 他們只能到達左右兩邊第一個比自己高的山峰，
思路：
? 整理題意后明顯可以發現是一個單調堆疊題目，對于每個i，預處理出左右第一個可達的山峰，就可以將題目轉化成一個DAG上的最長路問題，可以通過記憶化搜索的方式解出，
實作：
? 在實作的程序中，樣例無法通過，原來是疏忽了一個條件，因為山峰的值陣列是嚴格遞增或者嚴格遞減的，所以對于 8 8 8 8 6，我們應該從6跳到最左邊的8，才能獲得最大的收益，
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 1000005;
int n;
ll f[N];
int h[N], g[N];
int l[N], r[N]; //左邊第一個比h[i]大的，右邊第一個比h[i]大的
vector<int> G[N];
void init()
{
for(int i = 1; i <= n; i ++)
f[i] = -1, G[i].clear(), l[i] = r[i] = -1;
}
void dfs(int u) //DAG上DP
{
if(f[u] != -1) return;
f[u] = 0;
for(int v : G[u])
{
if(f[v] == -1) dfs(v);
f[u] = max(f[u], f[v] + abs(g[u] - g[v]));
}
}
void solve()
{
scanf("%d", &n);
init();
for(int i = 1; i <= n; i ++)
scanf("%d", &h[i]);
for(int i = 1; i <= n; i ++)
scanf("%d", &g[i]);
stack<int> stk1, stk2;
int idx;
for(int i = 1; i <= n; i ++)
{
idx = i;
while(stk1.size() && h[stk1.top()] <= h[i])
{
if(h[i] == h[stk1.top()]) idx = stk1.top();
stk1.pop();
}
if(stk1.size()) l[i] = stk1.top();
stk1.push(idx);
}
for(int i = n; i >= 1; i --)
{
idx = i;
while(stk2.size() && h[stk2.top()] <= h[i])
{
if(h[i] == h[stk2.top()]) idx = stk2.top();
stk2.pop();
}
if(stk2.size()) r[i] = stk2.top();
stk2.push(idx);
}
for(int i = 1; i <= n; i ++)
{
if(l[i] != -1) G[i].pb(l[i]);
if(r[i] != -1) G[i].pb(r[i]);
}
for(int i = 1; i <= n; i ++)
dfs(i);
for(int i = 1; i <= n; i ++)
printf("%lld ", f[i]);
puts("");
}
signed main()
{
int _ = 1;
scanf("%d", &_);
while(_--)
solve();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/505951.html
標籤：其他
下一篇：2022-09-08隨筆