WHU 1537 Stones I

题目见： http://acm.whu.edu.cn/land/problem/detail?problem_id=1537

　　这个题相当无语，学长给的解法是：枚举取的个数k，然后对每个k贪心，取其中的最大值。

　　我想思路应该是这样：结果与选取的顺序无关，只和最终选取的数量有关。

　　所以，就枚举最终选取的数量k，在这种情况下，每个物品的价值就是固定的。

　　所以，在这种情况下，最优策略就一定是选取价值最大的前k个。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <functional>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 1050;
 9 
10 int a[MAXN], b[MAXN], c[MAXN];
11 int n;
12 
13 int main() {
14     #ifdef Phantom01
15         freopen("WHU1537.txt", "r", stdin);
16     #endif // Phantom01
17 
18     while (scanf("%d", &n)!=EOF) {
19         if (0==n) break;
20 
21         for (int i = 0; i < n; i++)
22             scanf("%d%d", &a[i], &b[i]);
23         int ans = 0;
24         for (int k = 1; k <= n; k++) {
25             for (int i = 0; i < n; i++)
26                 c[i] = a[i] - k*b[i];
27             sort(c, c+n, greater<int>());
28             int tmp = 0;
29             for (int i = 0; i < k; i++)
30                 tmp += c[i];
31             ans = max(ans, tmp);
32         }
33         printf("%d
", ans);
34     }
35 
36     return 0;
37 }