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

前言

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

思路

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

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

那么 考虑转移

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

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

CODE

#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>a[i];

    f[0][0] = 1;///前0个数 总和为0
    
    for(int i=1;i