传送门
题目描述
牛牛喜欢整数序列，他认为一个序列美丽的定义是
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
输入
复制
2 3 -1
输出
复制4
4
示例2
输入
复制
3 5 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][之前和]
讨论一下枚举的界限问题文章来源：https://www.toymoban.com/news/detail-537196.html
AC代码：文章来源地址https://www.toymoban.com/news/detail-537196.html
#include<bits/stdc++.h>
#define int long long
using 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<=n;i++){
cin>>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<=1600-j;s++){
if(j>=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<=1600-a[i];s++){
if(a[i]>=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<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}到了这里，关于美丽序列（Dp）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
