呵呵，刚好看到你的回复
这里没有代码格式
自己复制ALT + F8一下
#include<stdio.h>
#include<string>
#define Min(a,b) a>b?b:a
struct DP{
int score;
int next;
int time;
}dp[32768];
struct Homework{
int deadlion,time;
char name[101];
}hw[15];
char ans[15][101];
int n;
void dfs(int k)
{
int i,min,cnt,time,d=k,id,score,next,t;
char ch[16];
memset(ch,'0',sizeof(ch));
i = 14;
d = k;
cnt = 0;
ch[15] = 0;
while(d)
{
if(d&1)
{
cnt += d&1;
ch[i] = (d&1) + '0';
id = i;//如果只有一个1，id可以记录下1的位子
}
i --;
d >>= 1;
}//转化成二进制
if(cnt == 1)//最底下的情况,只完成了一种作业
{
id = 14 - id;
if(hw[id].deadlion >= hw[id].time)
dp[k].score = 0;
else
dp[k].score = hw[id].time - hw[id].deadlion;
dp[k].time = hw[id].time;
dp[k].next = id;
return ;
}
min = 0x7FFFFFFF;
for(i=0;i<15;i++)
{
if(ch[i]=='1')
{
id = 14 - i;
int kk = k - (1<<id);
if(dp[kk].time == -1)
dfs(kk);
time = dp[kk].time + hw[id].time;
score = dp[kk].score;
if(hw[id].deadlion < time)
score += (time-hw[id].deadlion);
if(score < min || score == min && strcmp(hw[id].name,hw[next].name)<0)
{
if(score<min)
next = id;
min = score;
t = time;
}
}
}
dp[k].score = min;
dp[k].next = next;
dp[k].time = t;
}
int main()
{
int T,i,k;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
k = (1<<n)-1;//一共有这么多可能
for(i=0;i<=k;i++)
dp[i].time = -1;
for(i=0;i<n;i++)
scanf("%s%d%d",hw[i].name,&hw[i].deadlion,&hw[i].time);
dfs(k);
printf("%d\n",dp[k].score);
//输出名字
for(i=0;i<n;i++)
{
strcpy(ans[i],hw[ dp[k].next ].name);
k = k - (1<<(dp[k].next));
}
for(i=n-1;i>=0;i--)
puts(ans[i]);
}
return 0;
}
回复 更多评论