洛谷P1077 [NOIP2012 普及组] 摆花
作者:
Air1222
,
2024-04-07 17:23:37
,
所有人可见
,
阅读 6
//爆搜
#include <iostream>
using namespace std;
const int N = 110,MOD=1e6+10;
int n,m;
int a[N];
int ans;
void dfs(int u,int k)
{
if(k==m)
{
ans=(ans+1)%MOD;
return;
}
if(u>n) return;
for(int i=0;i<=a[u];i++)
dfs(u+1,k+i);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1,0);
cout<<ans;
return 0;
}
//因为搜索顺序满足拓扑序
//及当第i种花被算选且此时已经选择k个时后面的子树状态是唯一确定的
//因此可以用记忆化搜索
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110,MOD=1e6+7;
int n,m;
int a[N];
int f[N][N];
int dfs(int u,int k)
{
if(k==m) return 1;//别忘了u>n判断在后,debug好长时间...
if(u>n) return 0;
if(k>m) return 0;
if(f[u][k]) return f[u][k];
int ans=0;//记忆化搜索一般都为累加子树的所有情况,从后往前推
for(int i=0;i<=a[u];i++)
ans=(ans+dfs(u+1,k+i))%MOD;
f[u][k]=ans;
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<dfs(1,0);
return 0;
}
//DP,类似于背包,体积限制为选择的花的数量
#include <iostream>
using namespace std;
const int N = 110,MOD=1e6+7;
int f[N][N];
int a[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0][0]=1;
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<<f[n][m];
return 0;
}