本文共 1083 字，大约阅读时间需要 3 分钟。
http://acm.whu.edu.cn/land/problem/detail?problem_id=1537
告诉你n个物品， n<=1000， 每个物品有两个值a和b， 每选择一个物品， 所有物品包括这件选中的物品的a 就要减去这件选中物品的 b值，问你选中物品的a的总和Max最大为是多少。
主要是看题面的条件， 既然n<=1000就可能存在O（n^2)复杂度的解。
由于物品数不会超过1000， 就可以枚举放入的物品总数x， 用n^2的复杂度解决问题。
首先从1到n枚举放入的物品总数为x，那么假如放了第k件物品，就可以使得总收益增加a[k]-b[k]*x，所以就对所有n件物品按a[k]-b[k]*x从大到小排一个序，再将前x件物品计算好，更新一下Max。最后把Max输出来。
#include#include #include using namespace std;const int maxn = 1100;struct node{ int a, b;}no[maxn];int num;bool cmp(const node &x, const node &y){ return x.a - x.b * num > y.a - y.b * num;}int main(){// freopen("data.in", "r", stdin); int ans, n, sum; while(scanf("%d", &n) != EOF && n != 0) { for(int i = 0; i < n; i++) scanf("%d%d", &no[i].a, &no[i].b); ans = 0; for(num = 1; num <= n; num++) { sort(no, no+n, cmp); sum = 0; for(int i = 0; i < num; i++) { sum += (no[i].a - no[i].b * num); } ans = max(ans, sum); } printf("%d\n", ans); } return 0;}
转载地址：http://xbhrb.baihongyu.com/