题意
全连（fc）
【题目背景】
还记得若干年前那段互相比较《克罗地亚狂想曲》的分数的日子吗？
【题目描述】
E.Space 喜欢打音游。
但是他技术不好，总是拿不到全连（Full Combo）。
现在他面前有一份乐谱，乐谱的其中一段有 n 个连续的单键音符。
相邻两个音符的到来时间均相等，我们可以认为第 i 个音符会在第 i 个时刻到来。
点击一个音符，E.Space 需要一段准备时间来进行移动手指之类的操作。由于音符的位置和周围情况不同，点击每个音符的准备时间也不同。
在一个音符的准备时间内，E.Space 没法做到去点击其它音符，但是不同音符的准备时间范围可以互相重叠。形式化地，令第 i 个音符的准备时间为 ti 个单位时间，那么如果 E.Space 选择去点击第 i 个音符，那么他就没法点击所有到来时刻在 (i − ti, i + ti)中的音符。
为了获得更高的分数，E.Space 还计算了每个音符的性价比。一个音符的性价比等于点击这个音符得到的分数除以 E.Space 点击它所需要的准备时间。
E.Space 就不指望全连了，他只是想让你帮他计算一下他最多可以得到多少分数。
【输入格式】
从文件 fc.in 中读入数据。
第一行一个正整数 n 。
第二行 n 个正整数，第 i 个正整数表示 ti 。
第三行 n 个正整数，第 i 个正整数表示第 i 个音符的性价比 ai。
【输出格式】
输出到文件 fc.out 中。
一行一个正整数，表示 E.Space 可能达到的最高分数。
【样例 1 输入】
5
2 3 2 1 2
3 1 2 9 4
【样例 1 输出】
18
【样例 1 解释】
E.Space 可以选择点击第 1, 3, 5 个音符，分数为 2 × 3 + 2 × 2 + 2 × 4 = 18 。
【子任务】
保证 \(t_i ≤ n ，a_i ≤ 10^9\)
| 测试点编号 | n ≤ |
|---|---|
| 1 | 5 |
| 2 | 10 |
| 3 | 15 |
| 4 | 20 |
| 5 | 1000 |
| 6 | 2000 |
| 7 | 5000 |
| 8 | 10000 |
| 9 | 30000 |
| 10 | 50000 |
| 11 | 100000 |
| 12 | 200000 |
| 13 | 500000 |
| 14 | 800000 |
| 15 | 1000000 |
| 16 | 1000000 |
| 17 | 100000 |
| 18 | 100000 |
| 19 | 1000000 |
| 20 | 1000000 |
对于最后 4 个测试点，保证对于任意的 i, j 有 \(t_i = t_j\) 。
分析
考场90分
看出来是偏序题，发现树套树会炸空间，于是去想cdq分治。
\(i-t_i\)小的应该先更新，于是初始化按\(i-t_i\)排序。然后考虑更新顺序，cdq分治应该使用中序遍历的方式。cdq过程中先做左半区间，把左半区间按照\(i\)排序，然后更新右半区间，最后做右半区间。
时间复杂度\(O(n \log^2 n)\)
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=1e6+1;
int n;
ll s[N];
#define lowbit(x) (x&-x)
il void init(int p){
for(rg int i=p;i<=n;i+=lowbit(i)) s[i]=0;
}
il void insert(int p,ll v){
for(rg int i=p;i<=n;i+=lowbit(i)) s[i]=max(s[i],v);
}
il ll query(int p){
ll ans=0;
for(rg int i=p;i;i-=lowbit(i)) ans=max(ans,s[i]);
return ans;
}
struct node{
int id,t;
ll v,ans;
il bool operator<(co node&b)co {return id-t<b.id-b.t;}
}a[N],b[N];
void solve(int l,int r){
if(l==r) return void(a[l].ans=max(a[l].ans,a[l].v));
int mid=l+r>>1;
solve(l,mid);
for(rg int i=l,j=mid+1,p=l;p<=r;++p){
if(i>mid||j<=r&&a[i].id>a[j].id-a[j].t) a[j].ans=max(a[j].ans,query(a[j].id-1)+a[j].v),++j;
else {if(a[i].id+a[i].t-1<=n) insert(a[i].id+a[i].t-1,a[i].ans); ++i;}
}
for(rg int i=l;i<=mid;++i) if(a[i].id+a[i].t-1<=n) init(a[i].id+a[i].t-1);
solve(mid+1,r);
for(rg int i=l,j=mid+1,p=l;p<=r;++p){
if(i>mid||j<=r&&a[i].id>a[j].id) b[p]=a[j++];
else b[p]=a[i++];
}
copy(b+l,b+r+1,a+l);
}
int main(){
freopen("fc.in","r",stdin),freopen("fc.out","w",stdout);
read(n);
for(rg int i=1;i<=n;++i) a[i].id=i,read(a[i].t);
for(rg int i=1;i<=n;++i) a[i].v=read<ll>()*a[i].t;
sort(a+1,a+n+1),solve(1,n);
ll ans=0;
for(rg int i=1;i<=n;++i) ans=max(ans,a[i].ans);
printf("%lld\n",ans);
return 0;
}
标解
这是一道中规中矩的序列DP+1D1D的优化
没有多少思维难度
是一道开场就可以切掉的题
没想到改变插入顺序……
#include<bits/stdc++.h>
using namespace std;
#define gc c=getchar()
#define r(x) read(x)
#define ll long long
template<typename T>
inline void read(T&x){
x=0;T k=1;char gc;
while(!isdigit(c)){if(c=='-')k=-1;gc;}
while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}
const int N=1e7+5;
int n;
ll c[N];
inline void insert(int x,ll v){
for(int i=x;i<=n;i+=(i&-i)){
c[i]=max(c[i],v);
}
}
inline ll query(int x){
if(x<=0)return 0;
ll ret=0;
for(int i=x;i;i^=(i&-i)){
ret=max(c[i],ret);
}
return ret;
}
ll f[N];
int t[N];
int a[N];
vector<int>G[N];
int main(){
freopen("fc.in","r",stdin);
freopen("fc.out","w",stdout);
r(n);
for(int i=1;i<=n;++i){
r(t[i]);
if(i+t[i]<=n)G[i+t[i]].push_back(i);
}
for(int i=1;i<=n;++i){
r(a[i]);
for(int j=0;j<G[i].size();++j){
insert(G[i][j],f[G[i][j]]);
}
f[i]=query(i-t[i])+(ll)a[i]*t[i];
}
ll ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,f[i]);
}
printf("%lld\n",ans);
return 0;
}