我們可以從幾個(gè)種類(lèi)中選取競(jìng)賽的題目,這里的一個(gè)"種類(lèi)"是指一個(gè)競(jìng)賽題目的集合,解決集合中的題目需要相同多的時(shí)間并且能得到相同的分?jǐn)?shù)。你的任務(wù)是寫(xiě)一個(gè)程序來(lái)告訴USACO的職員,應(yīng)該從每一個(gè)種類(lèi)中選取多少題目,使得解決題目的總耗時(shí)在競(jìng)賽規(guī)定的時(shí)間里并且總分最大。輸入包括競(jìng)賽的時(shí)間,M(1 <= M <= 10,000)(不要擔(dān)心,你要到了訓(xùn)練營(yíng)中才會(huì)有長(zhǎng)時(shí)間的比賽)和N,"種類(lèi)"的數(shù)目1 <= N <= 10,000。后面的每一行將包括兩個(gè)整數(shù)來(lái)描述一個(gè)"種類(lèi)":

第一個(gè)整數(shù)說(shuō)明解決這種題目能得的分?jǐn)?shù)(1 <= points <= 10000),第二整數(shù)說(shuō)明解決這種題目所需的時(shí)間(1 <= minutes <= 10000)。

你的程序應(yīng)該確定我們應(yīng)該從每個(gè)"種類(lèi)"中選多少道題目使得能在競(jìng)賽的時(shí)間中得到最大的分?jǐn)?shù)。

來(lái)自任意的"種類(lèi)"的題目數(shù)目可能是任何非負(fù)數(shù)(0或更多)。

計(jì)算可能得到的最大分?jǐn)?shù)。

第 1 行: M, N--競(jìng)賽的時(shí)間和題目"種類(lèi)"的數(shù)目。

第 2-N+1 行: 兩個(gè)整數(shù):每個(gè)"種類(lèi)"題目的分?jǐn)?shù)和耗時(shí)。

單獨(dú)的一行包括那個(gè)在給定的限制里可能得到的最大的分?jǐn)?shù)。

題目翻譯來(lái)自NOCOW。

USACO Training Section 3.1

題解

這是道完全背包模板題。把競(jìng)賽時(shí)間看做背包容量，每個(gè)種類(lèi)的題目看做物品，每個(gè)物品可以被選擇，也可以不選。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <string.h>
 6 
 7 using namespace std;
 8 
 9 const int    MAXN = 1e5 + 5;
10 int        m, n, s[MAXN], t[MAXN], f[MAXN];
11 
12 int main()
13 {
14     cin >> m >> n;
15     for ( int i = 1; i <= n; i++ )
16     {
17         cin >> s[i] >> t[i];
18     }
19     for ( int i = 1; i <= n; i++ )
20     {
21         for ( int j = t[i]; j <= m; j++ )
22         {
23             f[j] = max( f[j], f[j - t[i]] + s[i] );
24         }
25     }
26     cout << f[m] << endl;
27     return(0);
28 }