Doing Homework
题目大意:
有一个人想完成n种作业,有n行,每行一个课程名称,课程提交截至时间,课程完成所需时间,现在以什么顺序完成所有作业所超时间最少和所超最少时间,且最少时间相同时字典序小的在前,给定数据的字典序是上升的。
数据范围:
解题思路:
n个数的不同排列共有n!种,15!达大小,但是却可以枚举每个状态,从的每个状态,对于2进制下每个位置,1代表已选,0代表未选,所以可以从当前状态加入任意一个未选过的作业,往后推得所有情况,转移方程为具体见代码。
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 1 << 15;
struct DP {
int c, reduce, pre;//分别为总花费,超时量,前一个状态。
}dp[maxn + 5];
bool vis[maxn + 5];//记录状态是否已出现过
int T, n;
struct NOOD {
char s[105];
int d, c;
}ans[20];
void print(int x) {//打印选择顺序
if(x == -1)return ;
print(dp[x].pre);
for(int i = 0; i < n; i++) {
if(vis[i])continue;
if(x & (1 << i)) {
printf("%s
", ans[i].s);
vis[i] = 1;
}
}
}
int main() {
scanf("%d", &T);
while(T--) {
memset(vis, 0, sizeof(vis));
memset(dp, 0, sizeof(dp));
scanf("%d", &n);
for(int i = 0; i < n; i++)scanf("%s%d%d", ans[i].s, &ans[i].d, &ans[i].c);
int len = 1 << n;//总状态数
dp[0].pre = -1;
dp[0].c = dp[0].reduce = 0;
vis[0] = true;
for(int i = 0; i < len; i++) {
for(int j = 0; j < n; j++) {
int x = 1 << j;
if(i & x)continue;//若不为0,说明当前状态已包含第j种作业
int t = x | i;//将第j种作业加入的状态
dp[t].c = dp[i].c + ans[j].c;//总花费增加
int reduce = dp[t].c - ans[j].d;//仅对于作业j,将超时多少
if(reduce < 0)reduce = 0;
reduce += dp[i].reduce;//总超时
if(vis[t]) {//如果状态已出现
if(reduce < dp[t].reduce) {
dp[t].reduce = reduce;
dp[t].pre = i;
}
}
else {//第一次出现
vis[t] = true;
dp[t].reduce = reduce;
dp[t].pre = i;
}
}
}
printf("%d
", dp[(1 << n) - 1].reduce);
memset(vis, 0, sizeof(vis));
print((1 << n) - 1);
}
return 0;
}