題目

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("%I64d\n", ans + f[m]);
    return 0;
}