AT2037 题解

Night_sea_64 · 2022-08-24 15:41:53 · 题解

计数型 01 背包。

因为要算平均数，但是在状态中直接记录平均数的值是不可能的，因为有小数。所以状态中存两个值：f_{k,j} 表示取了 k 个数，和为 j 的方法数。

转移就是 f_{k,j}=f_{k,j}+f_{k-1,j-a_i}。k-1 是这个数还没取，也就是少取了一个，j-a_i 表示当前这个和减去现在这个值也就是之前的和。

注意就是枚举 k 和 j 时反着循环，要设初值，还要开 long long。以下是 AC 代码：

#include<iostream>
using namespace std;
int a[55];
long long f[55][2505];
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=2500;j>=a[i];j--)
            for(int k=n;k>=1;k--)
                f[k][j]+=f[k-1][j-a[i]];
        //注意这两重循环是反着的，否则会从已经改过的值转移来。
    long long sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=2500;j++)
            sum+=(j*1.0/i==double(m))*f[i][j];
    //如果平均值等于 m 就将 sum 加上 f[i][j]。
    cout<<sum<<endl;//AT 加换行。
    return 0;
}