題意：

• 給一數組a，可對其中$a_i$進行如下操作：將$a_i$拆成兩數之和，然后代替$a_i$加入數組中。設一個數組的 $extreme$ $value$ 指的是：使得數組單調不下降的最小操作次數。據此，求a數組的所有子數組的 $extreme$ $value$ 之和

思路：

• 先考慮一個數組，顯然，將末尾元素拆分是沒有意義的，且會使答案增大。而對于中間元素，例如 $...[17],5,10,23,...$ ，如果它違反了單調不下降的規則，就必須進行拆分，可以有多種拆法，但使得其中最小元素盡可能大，是最優的拆法。例如，拆成$(4,4,4,5)$比$(3,3,3,3,5)$更好，因為這可能減少前面需要的操作數量，因此，相當于讓拆分成的元素盡可能接近，且數量盡可能少，又要讓其中最大的小于$a_{i+1}$，那么，對于當前的數$a_i$和下一個數$a_{i+1}<a_i$，我們應當拆分，例如這里17應當分為$?17/5?=4$個數，所以最小數是$?17/4?=4$。顯然，如果$a_i$比$a_{i+1}$小，則認為我們將它“拆分成一個數”
• 這樣掃一遍下來，以$O(n)$解決了求解單個數組的問題，但是，子數組的數量是$n^2$數量級，不能全部這樣求解
• 考慮$d{p}_{i,x}$是第$i$個數被拆分成最小元素為$x$的若干個數，并且以$x$開頭的非遞減數列的數量。有$d{p}_{i?1,y}$ += $d{p}_{i,x}$，因此可以轉化。
• 一個數$n$拆分為最小元素$x$ $\in$ {$n$,$?n/2?$,$?n/3?$,…,$1$}，這個集合中元素個數不是n個，而是$O(n^{1/2})$數量級的，這一點在整除分塊的技巧中也有使用。
• 最終我們根據$dp$數組統計答案。對于$dpi+1,x$，它對答案的貢獻是$i?d{p}_{i+1,x}?(?a_i/a_{i+1}??1)$，這是因為有$i?d{p}_{i+1,x}$個數列，每個數列對$a_i$執行這樣的拆分

#include <iostream> #include <unordered_map>using namespace std;typedef long long ll;const int N = 1e5 + 10; const ll mod = 998244353;int a[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _;cin >> _;while (_ -- ){int n;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];unordered_map<int, int> dp[2];ll ans = 0;for (int i = n; i >= 1; i -- ){dp[1][a[i]] = 1;for (auto it : dp[0]){int t = ceil(a[i] * 1.0 / it.first);dp[1][a[i] / t] += it.second;ans += ((ll)i * it.second) * (t - 1);}ans %= mod;swap(dp[0], dp[1]);dp[1].clear();}cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Extreme Extension 思维，dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。