【题解】钱老板赶工

一开始看题还以为是个贪心，后来仔细看了一下发现并不是，然后发现任务数 $n(1\leq n \leq 20)$ ，就上状压dp了，
可以用一个大于0,小于(1<<n)的数字表示做了哪些任务，比如一共有8个任务，数字 $i$ 的二进制是00100110就表示做了第2，3，6个任务， $dp[i]$ 表示做了 $i$ 代表的这些任务的的最小延迟天数。
那 $dp[00100110]$ 其实是从以下的三种情况转化来的。

$dp[00000110]$
$dp[00100010]$
$dp[00100100]$

可以发现，转化出dp[i]的情况在数值上都比i小，因为是把i的某一个二进制位变成了0.所以只需要从0开始遍历到(1<<n)-1,推一遍dp值揪可以了。

#include<iostream>
#include<vector>
using namespace std;

const int INF= 0x3f3f3f3f;
int main()
{
    int n;
    cin >> n;
    int deadline[30];
    int cost[30];
    int MAXN = 1<<n;
    int sum = 0;
    for(int i = 0 ; i < n ; i++)
    {
        cin>>deadline[i]>>cost[i];
    }
    vector<int> dp(MAXN,INF);
    dp[0] = 0;
    for(int i = 0 ; i < MAXN ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(!(i&(1<<j)))
            {
                int next = i|(1<<j);
                int time = 0;
                for(int k = 0 ; k < n ; k++)
                {
                    if((1<<k)&i)
                    {
                        time+=cost[k];
                    }
                }
                int add = 0;
                dp[next]=min(dp[next],dp[i]+max(0,time+cost[j]-deadline[j]));
            }
        }
    }
    cout<<dp[MAXN-1]<<endl;;
    return 0;
}