篮球杯DP 数组切分

客官°小女子只卖身不卖艺 2024-03-26 14:37 95阅读 0赞

![3d02e6c22d80a8c14ded13015df9585d.png][]

思路：

数组划分型DP

基本形式就是：

先去枚举右端点r，再去枚举左端点l

当区间\[l,r\]满足条件时转移

在这里，当\[l,r\]中数的种类数为区间长度时转移

那么怎么去维护种类数，就是区间最大值-区间最小值

这里可以st表（纯纯多此亿举），也可以直接维护

**ST表：**

#include <bits/stdc++.h>
    #define int long long
    #define LL long long
    const int mxn=1e4+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    using namespace std;
    
    int n;
    int a[mxn],dp[mxn],f1[mxn][33],f2[mxn][33],lg[mxn];
    bool check(int l,int r){
        int k=lg[r-l+1];
        int mx=max(f2[l][k],f2[r-(1<<k)+1][k]);
        int mi=min(f1[l][k],f1[r-(1<<k)+1][k]);
        /*if(l==2&&r==3){
            cout<<k<<'\n';
            cout<<mi<<" "<<mx<<'\n';
        }*/
        return mx-mi==r-l;
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],f1[i][0]=a[i],f2[i][0]=a[i];
        for(int j=1;j<=30;j++){
            for(int i=1;i+(1<<(j-1))<=n;i++){
                f1[i][j]=min(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
                f2[i][j]=max(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
            }
        }
        //cout<<f2[2][1]<<'\n';
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=i;j>=1;j--){
                if(check(j,i)) dp[i]=(dp[i]+dp[j-1])%mod;
            }
        }
        cout<<dp[n]<<'\n';
    }
    void init(){
        lg[1]=0;
        for(int i=2;i<mxn;i++) lg[i]=lg[i>>1]+1;
        //for(int i=1;i<=10;i++) cout<<lg[i]<<" \n"[i==10];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

**直接维护**

#include <bits/stdc++.h>
    using namespace std;
    const int mxn = 1e4+5, mod = 1e9+7;
    int n, d[mxn], dp[mxn] = {1};
    int main(){
      scanf("%d", &n);  
      for(int i = 1; i <= n; ++i) scanf("%d", d+i);
      for(int m, M, i = 1; i <= n; ++i){    
        m = d[i], M = d[i];
        for(int j = i; j > 0; --j){
          m = min(m, d[j]);
          M = max(M, d[j]);
          if(M - m == i - j) dp[i] = (dp[i] + dp[j-1])%mod;
        }    
      }  
      printf("%d\n", dp[n]);
      return 0;
    }

[3d02e6c22d80a8c14ded13015df9585d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2a97286dfb254550b4dd3576e22f26c3.png