JZOJ 6068 全连

Deemo 玩家表示曾经尝试用类似套路（指题目中的准备时间）出一道题来着……

首先考虑 i 能够转移到 j 的条件是 i+ti≤j,i≤j−tj。
这个就是个二维偏序。

具体处理方式就是按照 1,…,n 转移，设 fi 表示到 i 的最大得分。
注意到由于 t 都是正整数，所以 j+tj≤i 是 j≤i 的充分条件。
所以可以把音符按照 j+tj 排序，然后在转移时同时维护一个指针一直跳而不必担心其是否未被转移过。
第二个条件仅需树状数组即可。

代码：

#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 1e6;
int n,t[N + 5],a[N + 5];
int A[N + 5];
inline bool cmp(int a,int b)
{
    return a + t[a] < b + t[b];
}
long long f[N + 5],c[N + 5];
inline void update(int x,long long k)
{
    for(;x <= n;x += lowbit(x))
        c[x] = max(c[x],k);
}
inline long long query(int x)
{
    if(x < 0)
        return 0;
    long long ret = 0;
    for(;x;x -= lowbit(x))
        ret = max(ret,c[x]);
    return ret;
}
long long ans;
int main()
{
    freopen("fc.in","r",stdin),freopen("fc.out","w",stdout);
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",t + i),A[i] = i;
    sort(A + 1,A + n + 1,cmp);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    for(register int i = 1,j = 1;i <= n;++i)
    {
        for(;j <= n && A[j] + t[A[j]] <= i;++j)
            update(A[j],f[A[j]]);
        ans = max(ans,f[i] = query(i - t[i]) + (long long)t[i] * a[i]);
    }
    printf("%lld\n",ans);
}