[Deeplearning] 2017篮球队

一道动态规划题

\(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;
}