题意：给出一个$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$相交的走路问题，可以通过组合数算出来。以后再来放代码吧
