随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stack>
 4 #include <cstring>
 5 using namespace std;
 6 #define inf 0x7ffffff
 7 struct data1 {
 8     char name[101];
 9     int deadline,day;
10 };
11 data1 subs[20];
12 struct data2 {
13     int score;
14     int pos;
15     int last;
16     int day;
17 };
18 data2 dp[40000];
19 
20 int main(){
21     freopen("in.txt","r",stdin);
22     int n,cas,i,j,now,last,temp,Max;
23     scanf("%d",&cas);
24     while (cas--){
25         scanf("%d",&n);
26         Max=(1<<n);
27         for(i=0;i<n;i++){
28             getchar();
29             scanf("%s %d %d",subs[i].name,&subs[i].deadline,&subs[i].day);
30         }
31         dp[0].score=dp[0].day=0;
32         for(i=1;i<Max;i++){
33             dp[i].score=inf;
34             for(j=n-1;j>=0;j--){
35                 if(i&(1<<j)){//第j个课程选中后
36                     now=i;
37                     last=i-(1<<j);
38                     temp=0;
39                     if(dp[last].day+subs[j].day>subs[j].deadline)
40                         temp=dp[last].day+subs[j].day-subs[j].deadline;
41                     if(dp[last].score+temp<dp[now].score){
42                         dp[now].score=dp[last].score+temp;
43                         dp[now].day=dp[last].day+subs[j].day;
44                         dp[now].pos=j;
45                         dp[now].last=last;
46                     }
47                 }
48             }
49         }
50         printf("%d\n",dp[Max-1].score);
51         stack<int> sta;
52         int p=Max-1;
53         while (p!=0){
54             sta.push(dp[p].pos);
55             p=dp[p].last;
56         }
57         while (!sta.empty()){
58             int no=sta.top();
59             sta.pop();
60             printf("%s\n",subs[no].name);
61         }
62     }
63 
64     return 0;
65 }
posted on 2012-07-10 00:17 Leo.W 阅读(107) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理