Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <algorithm>
- #include <fstream>
- #include <map>
- #include <stack>
- using namespace std;
- typedef long long ll;
- const int INF = 1e9;
- const int maxn = 21;
- int n, x;
- int a[maxn];
- pair<int, int> dp[1 << maxn];
- int main()
- {
- ios_base::sync_with_stdio(false);
- // ifstream cin("in.txt");
- cin >> n >> x;
- for(int i = 0; i < n; i++) {
- cin >> a[i];
- }
- dp[0] = make_pair(1, 0);
- for(int mask = 1; mask < (1 << n); mask++) {
- dp[mask] = make_pair(n + 1, 0);
- for(int i = 0; i < n; i++) {
- if(mask & (1 << i)) {
- pair<int, int> tmp = dp[mask ^ (1 << i)];
- if(tmp.second + a[i] <= x) {
- tmp.second += a[i];
- }
- else {
- tmp.first += 1;
- tmp.second = a[i];
- }
- dp[mask] = min(dp[mask], tmp);
- }
- }
- }
- cout << dp[(1<<n) - 1].first << endl;
- return 0;
- }
- /*
- 4 10
- 4 8 6 1
- 4 + 6
- 8 + 1
- f(taken) --> f(taken2)
- f(0000) --> f(1000) + 0
- f(1000) --> f(1010) + 1
- dp[taken][2]
- dp[taken][0] --> minimum weight sum of people till the previous move
- dp[taken][1] --> minimum number of elevator rides
- 8 6 4 1
- dp[taken] --> minimum number of elevator calls till this mask
- // 2 ^ 20 -->
- 27 40 16 50
- f(taken, left) --> f(taken2, left + a[j])
- f(1111)
- pair<int, int> dp[1 << n];
- dp[0] = make_pair(0, x)
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement