[NOIP 2012 普及组] 摆花

知识点

动态规划、有界计数、前缀和优化

解题思路

dp[j]表示处理若干花种后恰摆j盆的方案。加入上限a的花种时，ndp[j]=Σdp[j-k]（0≤k≤a且k≤j）。用前缀和或滑动窗口计算此和，模1000007。

正确性说明

每种花相邻且种类顺序固定，一组数量唯一决定排列。按最后一类花取k盆划分的方案互斥穷尽，故卷积转移准确。前缀和仅加速相同区间求和，不改变计数。

易错点

模数为1000007，不是1000000007；某类上限可为0；恰好m盆，不能累计所有≤m的状态。

复杂度

时间O(nm)，空间O(m)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;const int P=1000007;vector<int>d(m+1),v(m+1);d[0]=1;for(int i=0,a;i<n;i++){cin>>a;long long sum=0;for(int j=0;j<=m;j++){sum+=d[j];if(j-a-1>=0)sum-=d[j-a-1];sum=(sum%P+P)%P;v[j]=sum;}d.swap(v);}cout<<d[m]<<'\n';}