一道动态规划题
\(f_{i, j, k}\)表示前i个人里取j个，身高大于等于k的方法数
得到状态转移方程为\(f_{i, j, k} = f_{i − 1, j − 1, k − a_i}\)
由于这样空间不够，我们需要降维
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,m,h,a[MAXN];
int f[1000][MAXN];
int sum=0;
int main()
{
cin>>n>>m>>h;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=a[i];k<=sum;k++){
f[j][k]+=f[j-1][k-a[i]];
}
}
}
int ans=0;
for(int i=m*h;i<=sum;i++) ans+=f[m][i];
cout<<ans;
return 0;
}