1 条题解

  • 0
    @ 2025-10-16 9:53:25
    #include <iostream>
    #include <vector>
    using namespace std;
    
    // 每种砝码的质量
    int _g[] = {1, 2, 3, 5, 10, 20};
    
    int main()
    {
    	int i, j, Total = 0;
    	vector<int> G; // 记录每个砝码的质量
    	for (i = 0; i < 6; i++)
    	{
    		int g;
    		cin >> g;
    		for (j = 0; j < g; j++)
    		{
    			G.push_back(_g[i]); // 存储_g[i]质量的g个砝码
    		}
    	}
    	
    	vector<bool> DP(1001, false);
    	DP[0] = true; // 初始化,质量为0时为true
    	
    	for (int g : G)
    	{
    		for (j = 1000; j >= g; j--) // 总质量为1000向下循环
    		{
    			DP[j] = DP[j - g]; // 若j - g重量可以实现DP[j - g](为true)则重量j也可以实现
    		}
    	}
    	
    	for (bool dp : DP)
    	{
    		if (dp)
    		{
    			Total++; // 循环统计可实现的个数
    		}
    	}
    	
    	Total--; // 排除DP[0] 
    	
    	cout << "Total=" << Total << endl;
    	return 0;
    }
    
    

    信息

    ID
    395
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    398
    已通过
    183
    上传者