1 条题解

  • 0
    @ 2026-4-27 0:32:56

    考虑 dp。

    定义 fif_i 表示考虑前 ii 朵花,第 ii 朵必选,最多可以采几朵花。

    fi=max{fj}+1f_i = \max\{f_j\} + 1,其中 jili1,j+rj+1ij \le i - l_i - 1, j + r_j + 1 \le i

    max{fj}\max\{f_j\} 可以用树状数组维护最值。对于 jili1j \le i - l_i - 1 的限制,查询前缀 [1,ili1][1, i - l_i - 1]

    对于限制 j+rj+1ij + r_j + 1 \le i,发现 ii 只对 i+rii + r_i 之后的位置有贡献,因此在第 min(n,i+ri)\min(n, i + r_i) 个位置处理之后再将 fif_i 的值更新到树状数组上。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N = 200010;
    
    int n, l[N], r[N], tr[N], f[N], ans;
    vector<int> upd[N];
    
    int lowbit(int i) { return i & -i; }
    
    void update(int x, int k) {
    	for (int i = x; i <= n; i += lowbit(i)) tr[i] = max(tr[i], k);
    }
    
    int query(int x) {
    	int res = 0;
    	for (int i = x; i > 0; i -= lowbit(i)) res = max(res, tr[i]);
    	return res;
    }
    
    int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(nullptr);
    	
    	cin >> n;
    	for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    	
    	for (int i = 1; i <= n; i++) {
    		if (i - 1 <= l[i]) f[i] = 1;
    		else f[i] = query(i - l[i] - 1) + 1;
    		ans = max(ans, f[i]);
    		upd[min(n, i + r[i])].push_back(i);
    		for (int j : upd[i]) update(j, f[j]);
    	}
    	
    	cout << ans << "\n";
    	
    	return 0;
    }
    
    
    • 1

    信息

    ID
    10942
    时间
    3000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者