传送门

题目描述

牛牛喜欢整数序列,他认为一个序列美丽的定义是
1:每个数都在0到40之间
2:每个数都小于等于之前的数的平均值
具体地说:for each i, 1 <= i < N, A[i] <= (A[0] + A[1] + … + A[i-1]) / i.
3:没有三个连续的递减的数

现在给你一个序列,每个元素是-1到40,你可以将序列中的-1修改成任意的数,求你可以得到多少个美丽序列,答案对1e9+7取模

输入描述:

第一行输入一个整数n (1 ≤ n ≤ 40)第二行输入n个整数

输出描述:

输出一个整数

示例1

输入

复制

23 -1

输出

复制4

4

示例2

输入

复制

35 3 -1

输出

复制

2

示例3

输入

复制

3-1 0 40

输出

复制0

0

示例4

输入

复制

11-1 40 -1 -1 -1 10 -1 -1 -1 21 -1

输出

复制

579347890

备注:

子任务1: n <= 10子任务2: n <= 20子任务3: 无限制

思路:

首先状态设计:dp[i][j][k][s]

代表当前是第i个数字,且第i位选择数字j,

选择数字j后形成的递减序列长度为k

前i个数字的和为s

此时的方案数为dp[i][j][k][s]

显然分析,k只有1和2两种情况

1的时候就是当前选的数字比上一个大(所以说是当前递减数列的第一个数字)

2的时候就是当前选的数字比上一个小(不可能出现比上两个小的情况,因为这样序列长度就是3不合题意了)

那么状态转移方程也能写了

我们需要枚举一下上一个数字的值

依靠这个进行转移

先不管这个数字是否可以自定(如果要自定就再加一层循环枚举这个数字)

如果上一个的值大于当前值

dp[i][当前值][2][之前的和+当前值]+=dp[i-1][上一位值][1][之前的和]

因为这个时候形成递减数列了,所以递减数列的长度是2,就只转移到长度为2的状态

如果当前值大于等于上一个值

dp[i][当前值][1][之前的和+当前值]+=dp[i-1][之前值][1][之前和]+dp[i-1][之前值][2][之前和]

讨论一下枚举的界限问题

AC代码:

#include#define int long longusing namespace std;const int N=50;const int mod=1e9+7;int a[N];int dp[45][45][3][1605];void solve(){int n;cin>>n;for(int i=1;i>a[i];}if(a[1]==-1){for(int i=0;i<=40;i++){dp[1][i][1][i]=1;}}else dp[1][a[1]][1][a[1]]=1;for(int i=2;i<=n;i++){if(a[i]==-1){for(int j=0;j<=40;j++){for(int k=0;k<=40;k++){for(int s=j*(i-1);s=k){ dp[i][j][1][s+j]=(dp[i][j][1][s+j]+dp[i-1][k][1][s])%mod;dp[i][j][1][s+j]=(dp[i][j][1][s+j]+dp[i-1][k][2][s])%mod;}else {dp[i][j][2][s+j]=(dp[i][j][2][s+j]+dp[i-1][k][1][s])%mod;} }}} }else {for(int k=0;k<=40;k++){for(int s=a[i]*(i-1);s=k){dp[i][a[i]][1][s+a[i]]=(dp[i][a[i]][1][s+a[i]]+dp[i-1][k][1][s])%mod;dp[i][a[i]][1][s+a[i]]=(dp[i][a[i]][1][s+a[i]]+dp[i-1][k][2][s])%mod;}else{dp[i][a[i]][2][s+a[i]]=(dp[i][a[i]][2][s+a[i]]+dp[i-1][k][1][s])%mod;}}}}}int sum=0;for(int i=0;i<=40;i++){for(int j=n*i;j<=1600;j++){sum=(sum+dp[n][i][1][j])%mod;sum=(sum+dp[n][i][2][j])%mod;}}cout<<sum<>t;while(t--){solve();}}