幸福指数

题目如下：

a

看完题目没有想法，记得leetcode上面有一道也是相同的输入，但是求解的是最大任务完成数量，好像是set模拟的，但是这个题目是所有的任务，

都要完成，暴力的复杂度是15！，复杂度比较高，也没有贪心的性质，一直不会做。

后来在大神师弟的指导下：

他这么说：状压， 用一个2^15， dp[n]表示当前n对应二进制位1都完成了的最大幸福值， 然后和tsp差不多转移一下就行了。

我不是很懂tsp转移，然后大概写了一下自己的理解，这个题目也无从提交判断正误，只能这样了。

#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;

int t[20], d[20];
int n;
int dp[1 << 16];
bool in[1 << 16];
void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> d[i];
    }
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        in[u] = 0;
        int s = 0;
        for (int i = 0; i < n; i++) {
            if(u & (1 << i)) s += t[i];
        }
        for (int i = 0; i < n; i++) {
            if(u & (1 << i)) continue;
            int v = dp[u] + 100;
            if(s + t[i] > d[i]) {
                v -= s + t[i] - d[i];
            }
            int d = u | (1 << i);
            if(v > dp[d]) {
                if(!in[d]) {
                    in[d] = 1;
                    q.push(d);
                }
                dp[d] = v;
            }
         }
    }
    cout << dp[(1 << n) - 1] << endl;
}

int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}