G - Merchant Takahashi
G - Merchant Takahashi
首先考虑暴力 DP。
设最后一步走到编号 ii 的城镇的方案的最大收益为 fifi，则每次集市相当于是 fTi←fj−C∣Ti−j∣+Pi（1≤j≤n）。
这样每次可以通过枚举 j 来转移，这样总时间复杂度是 O(nm) 的，无法通过。
考虑优化 DP，先拆绝对值，把转移分为以下两类：
-
fTi←fj−C(Ti−j)+Pi（1≤j≤Ti），即 fTi←(fj+C⋅j)+(−C⋅Ti+Pi)。
注意到后面部分是定值而前面部分与 i 无关，j 的取值范围又是一段前缀，所以我们用树状数组维护 fj+C⋅j 的前缀最大值。
-
ffTi←fj−C(j−Ti)+Pi（Ti≤j≤n），即 fTi←(fj−C⋅j)+(C⋅Ti+Pi)。
同理我们用树状数组维护 fj−C⋅j 的后缀最大值。怎样用树状数组维护后缀信息？只需交换两个循环循序即可。
然后我们把 fTi 插入到树状数组的Ti 位置去。
初始状态为 f1=0，最后答案为 最大的f i。注意代码中的 fifi 表示的是上文的 fTi.
代码：
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n,m,c;
int dp[N];
int v[N],w[N];
int tr1[N];//求小于等于x的最大值
int tr2[N];//求大于等于x的最大值int lowbit(int x){return x&(-x);
}void add1(int x,int c){for(int i=x;i<=n;i+=lowbit(i)){tr1[i] = max(tr1[i],c);}return;
}int ask1(int x){int res = -inf;for(int i=x;i>=1;i-=lowbit(i)){res = max(res,tr1[i]);}return res;
}void add2(int x,int c){for(int i=x;i>=1;i-=lowbit(i)){tr2[i] = max(tr2[i],c);} return;
}int ask2(int x){int res = -inf;for(int i=x;i<=n;i+=lowbit(i)){res = max(res,tr2[i]);}return res;
}void solve(){cin>>n>>c;cin>>m;memset(tr1,-0x3f3f3f,sizeof(tr1));memset(tr2,-0x3f3f3f,sizeof(tr2));add1(1,c);add2(1,-c);dp[0] = 0;int ans = 0;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;int t = ask1(x) + (y-c*x);int tt = ask2(x) + (y+c*x);dp[i] = max(t,tt);ans = max(ans,dp[i]);add1(x,dp[i]+c*x);add2(x,dp[i]-c*x);}cout<<ans<<"\n";}signed main(){int T=1;//cin>>T;while(T--){solve();}return 0;
}