题目链接：
https://nanti.jisuanke.com/t/41007
Solution：
挺不错的一道dp。
不难发现砖块顺序不影响结果，所以直接记录下每个位置有多少个砖块落下，从左往右顺序处理即可
这道题很重要的一点是要想到去维护空位而不是维护有砖块的位置
令(dp[i])表示考虑令第(i)位为空，并且处理完前(i)位所有砖块的方案数，(f[i])处理完前(i)个位置后，产生了(i)个空位的方案数，(a[i])表示前(i)个位置砖块数的前缀和
若这个位置有砖块落下，跳过不处理就是了（也就是(dp[i]=0)）
考虑若这个位置没有砖块落下（(a[i]=a[i-1])），且有(i-1-a[i-1]>=0)（也就是这个位置存在作为空位的合法性），则有状态转移方程：
另外，之前我一直没想明白这个dp方程的正确性。因为(f[i])由于是用加法更新的，实际上是包含了之前每一次决策后产生(i)个空位的方案总和，而(dp[i])则应该只用到上一次的决策的结果啊。
换句话说，对于位置(j)，我刚处理完了(j)前面的一个位置(k)，此时产生了(i)个空位的方案数为(f[i])，然而之后处理位置(j)时，在(j)到(k)的过程中我在你(k)位置得到的(f[i])里的那些方案的基础上一通乱铺，就不能保证那些原本截止到(k)位置（即(1)到(k)）有(i)个空位的方案到(j)后仍然有(i)个空位啊。
然而我此时(f[i])却包含了那些方案，若用(f[i])去更新此时的(dp[j])，不就出问题了吗？
后来想想，如果我处理(j)时又调用到了这个(f[i])，显然，有(k-a[k]=j-1-a[j-1]=i)，也就是(j-1-k=a[j-1]-a[k]),即(（k，j）)这段区间上一定有(j-k-1)个砖落下，又因为(k)和(j)都不能放砖，我只能选择用这些砖把((k,j))这段区间铺满，不会有新空位产生，这样一来这个看起来有问题的(f[i])就是正确的了。
换言之，对于某个(f[i])，在转移过程中可能不是正确的，但如果满足调用到他的条件时，他就恰好是正确的了。这我认为是这个dp方程最巧妙的点
扯得有点多了，自己还是fw了......
#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int n,m;
int dp[1000005],f[1000005],a[1000005];
int main()
{
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x]++;
}
for(int i=1;i<=n+1;i++)
a[i]+=a[i-1];
f[0]=1;
for(int i=1;i<=n+1;i++)
{
if(a[i]==a[i-1])
{
if(i-1-a[i-1]>=0) dp[i]=f[i-1-a[i-1]];
if(i-a[i]>=0) f[i-a[i]]=(f[i-a[i]]+dp[i])%M;
}
}
printf("%d",dp[n+1]);
return 0;
}