Codeforces Round #701 (Div. 2)-F-水平線技巧優化dp

前言:

學習到一種新的優化 d p dp dp的技巧：水平線優化，

題目大意:略

題目思路:dp,前綴和優化,水平線優化，

考慮樸素的動態規劃： d p ( i , j ) dp(i,j) dp(i,j)代表填完前 i i i位且前綴和為 j j j的合法方案數.

要么符合操作一,第一種轉移: d p ( i , j ) ← d p ( i ? 1 , j ? b i ) dp(i,j)\leftarrow dp(i-1,j-b_i) dp(i,j)←dp(i?1,j?bi?)

要么符合操作二,第二種轉移: d p ( i , b i ) ← ∑ ? i n f i n f d p ( i ? 1 , j ) ? d p ( i ? 1 , 0 ) dp(i,b_i)\leftarrow \sum_{-inf}^{\ \ \ inf}dp(i-1,j)-dp(i-1,0) dp(i,bi?)←∑?inf inf?dp(i?1,j)?dp(i?1,0)

注:當 j = b i j=b_i j=bi?時,同時滿足操作一，操作二，所以得減去 d p ( i ? 1 , 0 ) dp(i-1,0) dp(i?1,0).

不難發現，第一種轉移就是將整個 d p dp dp陣列右移 b i b_i bi?.那么我們維護一個 o f f off off變數代表偏移量，每次 o f f ? = b i off -= b_i off?=bi?. 這樣我們優化掉第一維.

對于第二種轉移,我們維護一個 s s s代表 d p ( i ? 1 ) dp(i-1) dp(i?1)的總和，

然后 d p ( b i + o f f ) = s ? d p ( o f f + b i ) dp(b_i+off)=s-dp(off+b_i) dp(bi?+off)=s?dp(off+bi?) ---- 因為訪問 d p ( o f f ) dp(off) dp(off)等價于訪問 d p ( i , 0 ) dp(i,0) dp(i,0),那么訪問 d p ( o f f + b i ) dp(off+b_i) dp(off+bi?)等價于訪問 d p ( i ? 1 , 0 ) dp(i-1,0) dp(i?1,0)

時間復雜度計算:

根據上面的轉移我們不難發現，每次多出一個 b i b_i bi?，我們前綴和的總數至多增加一個.我們用map實作dp陣列，時間復雜度為: O ( n l o g n ) O(nlogn) O(nlogn)

AC代碼:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--){
        int n ; cin >> n;
        for (int i = 1 ; i <= n ; i++) cin >> a[i];
        map<ll,ll> dp;
        dp[0] = 1;
        ll s = 1 , off = 0 , add;
        for (int i = 1 ; i <= n ; i++){
            off -= a[i];
            add = (s - dp[off + a[i]] + mod) %mod;
            dp[a[i] + off] = (dp[a[i] + off] + add) % mod;
            s = (s + add) % mod;
        }
        cout << s << endl;
    }
    return 0;
}

參考博客：
https://blog.csdn.net/Fighting_Peter/article/details/113802017