CF競賽題目講解_CF1788E(DP + 前綴和 + 樹狀數(shù)組)
2023-02-27 16:11 作者:Clayton_Zhou | 我要投稿
AC代碼：
?https://codeforces.com/contest/1788/submission/195085759
題意：
給你一個n個整數(shù)的數(shù)組a1，a2，…，an。將S視為滿足以下條件的一組線段。
1. S的每個元素都應(yīng)該是[x，y]形式，其中x和y是1和n之間的整數(shù)，包括1和n，x≤y。
2. S中沒有兩個線段彼此相交。兩段[a，b]和[c，d]相交當且僅當存在整數(shù)x使得a≤x≤b且c≤x≤d。
3. 對于S中的每個[x，y]，ax+ax+1+…+ay≥0。
線段[x，y]的長度定義為y?x+1。f(S)被定義為S中每個元素的長度之和。
形式定義，f(S)=∑[x，y]∈S（y?x+1）。
注意，如果S為空，則f(S)為0。
題解：
DP + 前綴和 + 樹狀數(shù)組
標簽：
