【HDOJ】1031 Design T-Shirt

qsort直接排序。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 #define MAXNUM 1000
 6 
 7 typedef struct {
 8     int index;
 9     double statis;
10 } node_st;
11 
12 node_st nodes[MAXNUM];
13 
14 int comp1(const void *a, const void *b) {
15     node_st *p = (node_st *)a;
16     node_st *q = (node_st *)b;
17 
18     if (p->statis == q->statis)
19         return p->index - q->index;
20     else
21         return (q->statis>p->statis) ? 1:-1;
22 }
23 
24 int comp2(const void *a, const void *b) {
25     node_st *p = (node_st *)a;
26     node_st *q = (node_st *)b;
27 
28     return q->index - p->index;
29 }
30 
31 void output(int m) {
32     int i;
33     for (i=1; i<=m; ++i)
34         printf("index=%d, statis:%lf
", nodes[i].index, nodes[i].statis);
35 }
36 
37 int main() {
38     int n, m, k;
39     int i;
40     double tmp;
41 
42     while (scanf("%d %d %d", &n, &m, &k) != EOF) {
43         memset(nodes, 0, sizeof(nodes));
44         while (n--) {
45             for (i=1; i<=m; ++i) {
46                 scanf("%lf", &tmp);
47                 nodes[i].statis += tmp;
48             }
49         }
50         for (i=1; i<=m; ++i)
51             nodes[i].index = i;
52         qsort(nodes+1, m, sizeof(node_st), comp1);
53         //output(m);
54         qsort(nodes+1, k, sizeof(node_st), comp2);
55         //output(k);
56         for (i=1; i<=k; ++i) {
57             if (i == 1)
58                 printf("%d", nodes[i].index);
59             else
60                 printf(" %d", nodes[i].index);;
61         }
62         printf("
");
63     }
64 
65     return 0;
66 }

01背包也可解。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXNUM 1000
 5 
 6 double dp[MAXNUM];
 7 double statis[MAXNUM];
 8 char visit[MAXNUM][MAXNUM];
 9 
10 double max(double a, double b) {
11     return a>b ? a:b;
12 }
13 
14 int main() {
15     int n, m, k;
16     int i, j, p;
17     double tmp;
18 
19     while (scanf("%d%d%d",&n,&m,&k) != EOF) {
20         memset(dp, 0, sizeof(dp));
21         memset(statis, 0, sizeof(statis));
22         memset(visit, 0, sizeof(visit));
23 
24         while (n--) {
25             for (i=1; i<=m; ++i) {
26                 scanf("%lf", &tmp);
27                 statis[i] += tmp;
28             }
29         }
30 
31         for (i=1; i<=m; ++i) {
32             for (j=k; j>0; --j) {
33                 tmp = dp[j-1] + statis[i];
34                 if (dp[j] < tmp) {
35                     dp[j] = tmp;
36                     for (p=1; p<i; ++p)
37                         visit[j][p] = visit[j-1][p];
38                     visit[j][i] = 1;
39                 }
40             }
41         }
42         i = 0;
43         for (p=m; p>0; --p) {
44             if (visit[k][p]) {
45                 if (i)
46                     printf(" %d", p);
47                 else
48                     printf("%d", p);
49                 ++i;
50             }
51         }
52         printf("
");
53     }
54 
55     return 0;
56 }