[BZOJ1618][Usaco2008 Nov]Buying Hay 购买干草
试题描述
约翰的干草库存已经告罄，他打算为奶牛们采购H(1≤H≤50000)磅干草．
他知道N(1≤N≤100)个干草公司，现在用1到N给它们编号．第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅，需要的开销为Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包． 帮助约翰找到最小的开销来满足需要，即采购到至少H磅干草．
输入
第1行输入N和日，之后N行每行输入一个Pi和Ci．
输出
最小的开销．
输入示例
输出示例
数据规模及约定
见“试题描述”
题解
大视野上竟然有裸的背包。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 110
#define maxw 55010
#define oo 2147483647
int n, h, P[maxn], C[maxn], f[maxn][maxw]; int main() {
n = read(); h = read();
int mxp = 0;
for(int i = 1; i <= n; i++) P[i] = read(), C[i] = read(), mxp = max(mxp, P[i]); int H = h + mxp;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= H; j++) f[i][j] = oo;
for(int i = 0; i <= n; i++) f[i][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= H; j++) {
f[i][j] = f[i-1][j];
if(j - P[i] >= 0 && f[i][j-P[i]] < oo) f[i][j] = min(f[i][j], f[i][j-P[i]] + C[i]);
} int ans = oo;
for(int i = h; i <= H; i++) ans = min(ans, f[n][i]);
printf("%d\n", ans); return 0;
}