1 条题解

  • 2
    @ 2025-12-31 15:30:53

    (冷知识:这一题测试点名字和B1凑在一起刚好是remember的前缀)

    这种要求最优的一般先考虑dp

    于是我们可以发现这题可以转化为最多的数使得这几个数之和等于 MM

    还是一个比较裸的01背包问题。

    #include <cstdio>
    #include <iostream>
    using namespace std;
    
    int n,m,s;
    int a[201],dp[200005];
    
    int main() 
    {
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
        	cin>>a[i];
        	s+=a[i];
    	}
        int t=s-m;
        for(int s=1;s<=t;s++) dp[s]=-1e9;
        for(int i=1;i<=n;i++) 
    	{
            for(int sh=t;sh>=a[i];sh--) 
    		{
                if(dp[sh-a[i]]!=-1e9) 
    			{
                    dp[sh]=max(dp[sh],dp[sh-a[i]]+1);
                }
            }
        }
        cout<<dp[t];
        return 0;
    }
    
  • 1

信息

ID
10
时间
1000ms
内存
256MiB
难度
3
标签
递交数
196
已通过
21
上传者