G - Merchant Takahashi / F - Useless for LIS

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;
}

F - Useless for LIS

双倍经验：

算法依旧是树状数组加dp，f [ i ]表示前缀的最大长度，g [ i ] 表示后缀的最大长度，那么 i 的最大长度为 f [ i ] + g [ i ] - 1（减去重复元素）

 代码：

#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;
int a[N];
int f[N],g[N];
int tr1[N],tr2[N];
map<int,int>mp;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 = 0;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 = 0;for(int i=x;i<=n;i+=lowbit(i)){res = max(res,tr2[i]);}return res;
}void solve(){cin>>n;mp.clear();for(int i=0;i<=n+1;i++)f[i] = g[i] = 0;for(int i=0;i<=n+1;i++){tr1[i] = tr2[i] = 0;}for(int i=1;i<=n;i++)cin>>a[i];vector<int>b;//离散化for(int i=1;i<=n;i++){if(mp[a[i]])continue;mp[a[i]] = 1;b.push_back(a[i]);}sort(all(b));for(int i=1;i<=n;i++){int t = lower_bound(all(b),a[i]) - b.begin();a[i] = t+1;}int len = 0;//求前缀for(int i=1;i<=n;i++){f[i] = ask1(a[i]-1) + 1;add1(a[i],f[i]);len = max(len,f[i]);}/*for(int i=1;i<=n;i++){for(int j=i-1;j>=1;j--){if(a[i]>a[j]){f[i] = max(f[i],f[j]+1);len = max(len,f[i]);}}}*/for(int i=n;i>=1;i--){//求后缀g[i] = ask2(a[i]+1) + 1;add2(a[i],g[i]);}vector<int>ans;for(int i=1;i<=n;i++){if(f[i]+g[i]-1 == len){//如果前面的长度加上后面的长度为最长，那么就选ans.push_back(i);}}cout<<ans.size()<<"\n";for(int i=0;i<ans.size();i++){cout<<ans[i]<<" ";}cout<<"\n";}signed main(){int T=1;cin>>T;while(T--){solve();}return 0;
}