洛谷 P3052 [USACO12MAR]Cows in a Skyscraper G

题目链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[20][300000];//dp[i][j]第i组 状态为j的电梯已经有的重量
int w[20];//每头牛的重量
int n, m;
int main()
{
    
	cin >> n >> m;
	int u = 1<<n;
	for (int i = 0; i < n; i++)
		cin >> w[i];
	memset(dp, 0x3f,sizeof dp);//初始化为无穷大表示当前情况不存在
	for (int i = 0; i < n; i++)
		dp[1][1 << i] = w[i];//一开始初始化 每个牛都有可能在第一组，先放进去
	for (int i = 0; i <= n; i++)
    for (int j = 0; j < u; j++)//枚举每种状态000000-111111
    if (dp[i][j] != 0x3f3f3f3f)//如果当前状态存在
	 for (int k = 0; k < n; k++)
     {
    
			if (j & (1 << k))continue;//枚举状态j对于每个状态j判断这次里面有没有第k头牛，如果已经有第k头牛不参与讨论
			if (dp[i][j] + w[k] <= m)dp[i][j | (1 << k)] = min(dp[i][j] + w[k],dp[i][j|(1<<k)]);
			//没有第k头牛，且放入重量小于上限m就可以分到第i组，直接放入
			//j|(1<<k)就是把j的第k位变成1 例如j=100（2） k=(1<<1)=010(2) j|k=110
		 else dp[i + 1][j | (1 << k)] = min(dp[i][j | (1 << k)], w[k]);
			//对于状态j放不进去，就只能放入第i+1组，且状态变成有k，第i+1组现在没有牛所以为w[i],要与第i组有j取个最小值，保证为最优解，
	 }
	for (int i = 0; i <= n; i++)
	{
    
		if (dp[i][u - 1] != 0x3f3f3f3f)//第i组 j为全1 说明所有牛都被选中了，输出答案即可
		{
    
			cout << i; break;
		}
	}
}