test1018

考试总结

越来越菜了，该退役了

开题顺序极其不合理，高估了计算几何题做高分做法的可行性，实际上押dp更加可靠

这次时间分配也不合理，做不出还在死磕，罚坐了

T1

其实是个很弱的dp，但是有个沙比跳掉了

考虑设 $dp_{i,j,k,l}$ 表示前 $i$ 构成 $j$ 段，剩余几个偶数（当然奇数也可以），当前这一位是奇数还是偶数，然后式子比较长不放了看代码吧

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=303;
const int mod=1e9+7;
int n,m,a[N],cnt[N],dp[N][N][N][2],sum;
signed main(){
    freopen("2475.in", "r", stdin);
    freopen("2475.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]) cnt[a[i]&1]++;
    }
    cnt[0]=n/2-cnt[0];
    cnt[1]=ceil(1.0*n/2)-cnt[1];
    dp[0][0][0][0]=dp[0][0][0][1]=1;
    for(int i=1;i<=n;i++){
        if(!a[i]) sum++;
        for(int j=1;j<=m;j++){
            for(int k=0;k<=min(cnt[1],sum);k++){
                if(a[i]){
                    if(a[i]&1) {
                        dp[i][j][k][1]=(dp[i][j][k][1]+(dp[i-1][j-1][k][0]+dp[i-1][j][k][1])%mod)%mod;
                    }else{
                        dp[i][j][k][0]=(dp[i][j][k][0]+(dp[i-1][j][k][0]+dp[i-1][j-1][k][1])%mod)%mod;
                    }
                }
                else{
                    if(cnt[0]+k-sum+1>0) (dp[i][j][k][0]+=(((cnt[0]-(sum-k)+1)*(dp[i-1][j-1][k][1]+dp[i-1][j][k][0])%mod)%mod))%=mod;
                    if(k!=0) (dp[i][j][k][1]+=((cnt[1]-k+1)*(dp[i-1][j-1][k-1][0]+dp[i-1][j][k-1][1])%mod)%mod)%=mod;
                }
            }
        }
    }
    cout<<(dp[n][m][cnt[1]][0]+dp[n][m][cnt[1]][1])%mod;
}