WHU 1537 Stones I

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

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

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

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

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

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <functional>

 using namespace std;

 const int MAXN = ;

 int a[MAXN], b[MAXN], c[MAXN];

 int n;

 int main() {

     #ifdef Phantom01

         freopen("WHU1537.txt", "r", stdin);

     #endif // Phantom01

     while (scanf("%d", &n)!=EOF) {

         if (==n) break;

         for (int i = ; i < n; i++)

             scanf("%d%d", &a[i], &b[i]);

         int ans = ;

         for (int k = ; k <= n; k++) {

             for (int i = ; i < n; i++)

                 c[i] = a[i] - k*b[i];

             sort(c, c+n, greater<int>());

             int tmp = ;

             for (int i = ; i < k; i++)

                 tmp += c[i];

             ans = max(ans, tmp);

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

WHU 1537 Stones I

最新文章

热门文章