题意：给出一个$N$个数的序列$a_i$，其中$a_i=-1$表示第$i$个位置数字未知，问有多少种用非负整数代替$a_i$中$-1$的方法使得从全$0$序列经过以下操作若干次得到序列$a_i$：每一次从序列中选取一段区间$l,r$，需要保证$l$到$r$中所有数相同，将$[l+1,r-1]$内所有数$+1$。$N \leq 10^4 , a_i \leq 10^4$
第一次看题没看懂题目语文药丸
注意到一些性质：
$1.$首尾元素一定要是$0$
$2.$相邻两个元素的差一定为$-1,0,1$，因为一次操作可以产生$1$的差，而产生了差的地方就无法再进行操作了。
我们就可以将这道题抽象为：选择若干数量的$-1,0,1$，使得它们的和为$-1$的段的两边的数字的差。
到这里有两种做法：
$1.$DP
设$f_{i,j}$表示补了前$i$个$-1$，总和为$j$的方案数，每一次从$f_{i-1,j-1},f_{i-1,j}.f_{i-1,j+1}$转移，复杂度为$O(n^2)$
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
] , pot[];
int main(){
int N = read();
int a = read();
|| a == -)
dp[] = ;
; i <= N ; i++){
int a = read();
memset(pot , , sizeof(pot));
)
, N - i)){
cout << ;
;
}
else
pot[a] = ((a ? dp[a - ] : ) + dp[a] + dp[a + ]) % MOD;
else
; j <= min(i - , N - i) ; j++)
pot[j] = ((j ? dp[j - ] : ) + dp[j] + dp[j + ]) % MOD;
memcpy(dp , pot , sizeof(pot));
}
cout << dp[];
;
}
$2.$枚举+组合
预处理出所有连续的$-1$区间的长度和两边的数字的差，枚举$0$的个数，得到$-1$的个数和$1$的个数然后组合数。注意出现数字$<0$的情况，可以将取$-1$和$1$的过程分别看作向右一格和向上一格，就转换成了经典的从$(0,0)$开始不与$y=x-k$相交的走路问题，可以通过组合数算出来。以后再来放代码吧