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