题目

maxtir 最近买了一个背包。
maxtir 有一个容量为 m 的背包。sao 有 n 种物品,第 i 种物品的体
积为 ai ,价值为 b i 。sao 的每种物品都有无限多件,maxtir 可以任取。
在不超过背包容量的前提下,maxtir 要求所能获得的最大价值。

输入输出

输入格式

第1行输入两个正整数 n , m 。
第 2 至 n + 1行,每行输入两个正整数 ai , b i 。

输出格式

一个整数,表示 maxtir 所能获得的最大价值。
输入样例#1
2 15
3 2
5 3
输出样例#1
10
输入样例#2
3 70
71 100
69 1
1 2
140
输入/输出样例#3
见下发文件 backpack3.in/backpack3.out

数据范围

对于 20% 的数据, n , m ≤ 103 。
对于 40% 的数据, n , m ≤ 10 4 , ai , b i ≤ 10 。
对于 60% 的数据, n , m ≤ 105 。
对于 100% 的数据, n ≤ 10 6 , m ≤ 10 16 , ai , b i ≤ 100 。

分析

本人40pts的方法就不说了，放下正确分析：
按照noip的惯例,此题是一道送分题。
对于 60% 的数据,我们可以发现其实 n不大于100 ,若两种物品 ai 相同,
则 bi 较小的应该被舍弃,复杂度 o（am） 。
对于100 % 的数据,我们先证明一个引理:
引理:给定任意 n 个整数,它们之中存在若干个整数的和为 n 的
倍数。
证明:设 n 个整数为 a 1 , a 2 , a3 ,……, a n , (sn=sum_{i=1}^{n}ai)。
对于 s0 , s1 , s 2 , s 3 ,…… , sn 这 n+1 个数,至少有两个数模 n 相同,则
这两个数的差为 n 的倍数,证毕。
回到题目,设第 s 种物品为性价比最高的物品之中 ai 最小的物
品。设最优情况下有 x 件非第 s 种物品,则我们可以证明:
定理:存在一种最优情况使得 x < as 。
证明:若 x >= as ,则存在若干件物品的 ai 和为 as 的倍数,将这些物
品用第 s 种物品替换一定不劣。
于是这 x 件非第 s 种物品的 ai 和最大为 100a s 。于是我们选择
(n/as)-100 件第 s 种物品,剩下的空间做完全背包,复杂度 o(a^3)。

代码

#include <bits/stdc++.h> using namespace std;  typedef long long ll; const int m = 105; const int n = 2e4 + 50; ll m, ans, cnt, f[n]; int n, p[m][m];  struct data {     int x, y;          data(int _x = 0, int _y = 0): x(_x), y(_y) {}          bool operator < (const data &t) const {         int flag = x * t.y - y * t.x;         if (flag == 0) return x < t.x;         return flag < 0;     } } a[m];  int main() {     freopen("backpack.in", "r", stdin);     freopen("backpack.out", "w", stdout);     scanf("%d%i64d", &n, &m);     for (int x, y; n--; ) {         scanf("%d%d", &x, &y);         p[x][y] = 1;     }     n = 0;     for (int x = 1; x <= 100; x++) {         for (int y = 100; y >= 1; y--) {             if (p[x][y]) {                 a[++n] = data(x, y);                 break;             }         }     }     for (int i = 2; i <= n; i++)         if (a[i] < a[1]) swap(a[i], a[1]);     cnt = m / a[1].x - 100;     ans = cnt * a[1].y;     m -= cnt * a[1].x;     for (int i = 1; i <= n; i++)         for (int j = a[i].x; j <= m; j++)             f[j] = max(f[j], f[j - a[i].x] + a[i].y);     printf("%i64dn", ans + f[m]);     return 0; }