补题代码库

HDU 6728

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=6e3+50;

int dp[2][maxn],rval[2][maxn],cnt[2];
int c[maxn];
inline void add(int&x,int y){((x+=y)>=mod) and (x-=mod);}
void work(){
    int n;cin>>n;
    for(int i=1;i<n;++i)
        cin>>c[i];
    c[n]=inf;
    reverse(c+1,c+1+n);
    int now=0;
    dp[now][1]=1;
    rval[now][1]=c[1];
    cnt[now]=1;

    for(int i=2;i<=n;++i){
        int pre=now;
        now^=1;
        int &cp=cnt[pre],&cn=cnt[now];

        while(cp and rval[pre][cp]>c[i]){
            if(rval[pre][cp-1]<c[i]){
                rval[pre][cp]=c[i];
                break;
            }else --cp;
        }
        if(rval[pre][cp]<c[i]){
            ++cp;
            rval[pre][cp]=c[i];
            dp[pre][cp]=0;
        }
        if(rval[pre][cp-1]!=c[i]-1){
            --rval[pre][cp];
            rval[pre][++cp]=c[i];
            dp[pre][cp]=dp[pre][cp-1];
        }
//        for(int j=1;j<=cp;++j){
//            cout<<rval[pre][j]<<"-"<<dp[pre][j]<<endl;
//        }
//        return;
        cn=0;
        rval[now][cp]=c[i];
        dp[now][cp]=0;
        for(int j=cp-1;j;--j){
            rval[now][++cn]=c[i]-(rval[pre][j-1]+1);
            dp[now][cn]=dp[pre][j];
            add(dp[now][cp],(ll)dp[pre][j]*(rval[pre][j]-rval[pre][j-1])%mod);
        }
        ++cn;
        for(int j=1;j<=cn;++j)
            add(dp[now][j],dp[pre][cp]);
//        for(int j=1;j<=cn;++j){
//            cout<<rval[now][j]<<"-"<<dp[now][j]<<" ";
//        }
//        cout<<endl;
    }
    int ans=0;
    for(int i=1;i<=cnt[now];++i)
        ans=(ans+(ll)dp[now][i]*(rval[now][i]-rval[now][i-1]))%mod;
    cout<<ans<<"\n";

}
int main(){
#ifdef local
freopen("in.txt","r",stdin);
#endif // local
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)
        work();
    return 0;
}