暴雨rain

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
const int N=25010;
const int K=30;
const int MOD=(int)1e9+7;
int f[N][K][K][2],L[N][K],g[N][K][K][2],R[N][K],pos[N],h[N],n,k,tmp[K][2];
//快读
inline int read(){
    char c=getchar();
    int f=1,x=0;
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
    return f*x;
}
void update(int&x,int y){x+=y;if(x>=MOD)x-=MOD;}
void work(int f[N][K][K][2],int L[N][K])
{
    L[0][1]=0;
    rep(i,n)
    {
        int cnt=0,j=1;
        for(;j<=k+1&&j<=i&&L[i-1][j]>=h[i];L[i][++cnt]=L[i-1][j++]);
        if(cnt<=k+1)L[i][++cnt]=h[i],pos[i]=cnt;
        for(;j<=k+1&&j<=i&&cnt<=k+1;L[i][++cnt]=L[i-1][j++]);
    }
    f[0][1][0][0]=1;
    for(int i=0;i<n;i++)
    rep(x,k+1)
    if(x<=i+1)
    for(int j=0;j<=k;j++)
    for(int tag=0;tag<2;tag++)
    {
        if(L[i][x]<h[i+1])
        {
            update(f[i+1][pos[i+1]][j][tag],f[i][x][j][tag]);
            if(j<k)update(f[i+1][x+1][j+1][tag^(L[i][x]&1)],f[i][x][j][tag]);
        }
        else
        {
            update(f[i+1][x][j][tag^((L[i][x]-h[i+1])&1)],f[i][x][j][tag]);
            if(j<k)update(f[i+1][x][j+1][tag^(L[i][x]&1)],f[i][x][j][tag]);
        }
    }
}
int main()
{
    freopen("rain.in", "r", stdin);
    freopen("rain.out", "w", stdout);
    n=read(),k=read();
    rep(i,n) h[i]=read();
    work(f,L);
    reverse(h+1,h+n+1);
    work(g,R);
    int ans=0;
    rep(i,n)
    {
        rep(j,k+1)rep(tag,2)tmp[j-1][tag-1]=0;
        rep(x,k+1)if(x<=n-i+1&&L[n-i][x]<h[i])rep(j,k+1)rep(tag,2)update(tmp[j-1][tag-1],f[n-i][x][j-1][tag-1]);
        rep(x,k+1)if(x<=i&&R[i-1][x]<=h[i])rep(j,k+1)rep(tag,2)update(ans,1ll*g[i-1][x][j-1][tag-1]*tmp[k-(j-1)][tag-1]%MOD);
    }
    printf("%d
",ans);
    return 0;
}

考虑 DP，f[i][j][p][0/1]表示前 i 列，最大值是 j，且要求在后面存在一个高度至少为 j 的土地，已经铲平了 p 块，当前积水体积为奇数/偶数的方案数。由于至多会去掉 K 块土地，所以对于任意一个 i，j 的值只有 K+1 种。前缀后缀 DP 都做出来之后，枚举最终最大值所在列合并答案即可，注意处理多个最大值的情况。时间复杂度 O(NK^2)

//看不明白の代码+_+