钱老板赶工

[编程题]钱老板赶工

热度指数：1801 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

【注意：本题按通过的Case比例给分】

钱老板去国外度了个假，刚回到公司就收到了 n 封催促工作完成的邮件。

每项工作都有完成截止日期 deadline，钱老板做每项工作都会花去cost天，而且不能中断。
请你帮钱老板安排一下完成工作的顺序，以减少总的工作推迟时间。

输入描述:

第一行包含一个正整数 n(1<=n<=20)，表示工作数量。

接下来 n 行，每行包含两个整数，分别表示第 i 项工作的 deadline 和 cost。

输出描述:

一个数字，表示钱老板最少需要推迟几天才能完成所有工作。

示例1

输入

输出

说明

输入样例表示有 3 项工作。

第一项工作截止时间在第 3 天，需要 3 天时间完成。

第二项工作截止时间在第 8 天，需要 1 天时间完成。

第三项工作截止时间在第 3 天，需要 2 天时间完成。

因此合理的顺序是 1->3->2 或 3->1->2，均推迟 2 天。

算法知识视频讲解

Python

yQpy.

n=int(input())
a=[]
for _ in range(n): a.append(list(map(int,input().split())))
cache={}
def dfs(d,k):
    if k in cache:return cache[k]
    if k==(1<<n)-1:return 0
    res=1e9
    for i in range(n):
        if 1<<i&k!=0:continue
        res=min(res,dfs(d+a[i][1],k|1<<i)+max(0,a[i][1]+d-a[i][0]))
    cache[k]=res
    return res
print(dfs(0,0))

AC 85%

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int n = 0;
vector<pair<int, int>> a(25);
map<int, int> cache;
int dfs(int d, int k){
	if (cache.find(k) != cache.end()) return cache[k];
	if (k == (1 << n) - 1) return 0;
	int res = 1e9;
	for (int i = 0; i < n; i++){
		if (((1 << i)&k) != 0) continue;
		res = min(res, dfs(d + a[i].second, k | (1 << i)) + max(0, a[i].second + d - a[i].first));
	}
	cache[k] = res;
	return res;
}
int main()
{
	a.clear();
	cache.clear();
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
	cout << dfs(0, 0);
	return 0;
}

AC 90%