[Luogu] P1077 [NOIP2012 普及组] 摆花 计数类DP

计数类DP 没 线性DP 好分析啊

考虑最终状态 f[n][m] 前n个数中选出总和为m的方案

好家伙 直接就分析完了(二维状态到手)

那么 考虑转移

当前的可以由 上一层 所有可选方案转移
f[i][j] = f[i][j] + f[i-1][j-k]

是不是很难理解 ,难理解就对了 awa

#include 
using namespace std;
const int mod = 1e6+7;
const int N = 110;
int n,m,a[N],f[N][N];

void solve()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++)
    cin>>a[i];

    f[0][0] = 1;///前0个数 总和为0
    
    for(int i=1;i<=n;i++)
        for(int j= 0 ;j<=m;j++)
            for(int k = 0 ;k<=min(j,a[i]);k++)///每个都有选和不选的机会
            f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
    cout<