[usaco12mar]cows in a skyscraper g (state compression DP)

[USACO12MAR]Cows in a Skyscraper G - Luogu https://www.luogu.com.cn/problem/P3052 Continue to learn my state pressure dp, A good question for getting started with shape pressing is to continue to consider the state and the quantity in that state , I found that many questions of state pressure need to record the quantity of this state .

This problem is to record the current state of cattle taking the elevator , Then record the remaining of the last elevator in this state , Then start to think about whether other cows can come in , Or go to the next elevator .

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;


int n, W;
int a[MAXN];
int f[MAXN];
int g[MAXN];
int main() {
	int n, W;
	scanf("%d %d", &n, &W);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 1;
	g[0] = W;
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 1; j <= n; j++) {
			if (i & 1 << (j - 1))
				continue;
			if (g[i] >= a[j] && f[i | (1 << (j - 1))] >= f[i]) {
				f[i | (1 << (j - 1))] = f[i];
				if (f[i | (1 << (j - 1))] == f[i])
					g[i | (1 << (j - 1))] = max(g[i | 1 << (j - 1)], g[i] - a[j]);
				else
					g[i | (1 << (j - 1))] = g[i] - a[j];
			} else if (g[i] < a[j] && f[i | (1 << (j - 1))] >= f[i] + 1) {
				f[i | (1 << (j - 1))] = f[i] + 1;
				if (f[i | (1 << (j - 1))] == f[i] + 1)
					g[i | (1 << (j - 1))] = max(g[i | (1 << (j - 1))], W - a[j]);
				else
					g[i | (1 << (j - 1))] = W - a[j];
			}
		}
	}
	printf("%d\n", f[(1 << n) - 1]);
	return 0;
}