【题解-洛谷】P2918 [USACO08NOV] Buying Hay S

题目P2918 [USACO08NOV] Buying Hay S题目描述约翰的干草库存已经告罄他打算为奶牛们采购H ( 1 ≤ H ≤ 50000 ) H(1 \leq H \leq 50000)H(1≤H≤50000)磅干草。他知道N ( 1 ≤ N ≤ 100 ) N(1 \leq N\leq 100)N(1≤N≤100)个干草公司现在用1 11到N NN给它们编号。第i ii公司卖的干草包重量为P i ( 1 ≤ P i ≤ 5 , 000 ) P_i (1 \leq P_i \leq 5,000)Pi​(1≤Pi​≤5,000)磅需要的开销为C i ( 1 ≤ C i ≤ 5 , 000 ) C_i (1 \leq C_i \leq 5,000)Ci​(1≤Ci​≤5,000)美元。每个干草公司的货源都十分充足 可以卖出无限多的干草包。帮助约翰找到最小的开销来满足需要即采购到至少H HH磅干草。输入格式第1 11行两个整数N NN与H HH以空格分隔。第2 22行至第N 1 N1N1行其中第i 1 i1i1行包含两个整数P i P_iPi​与C i C_iCi​以空格分隔。输出格式一个整数表示 FJ 至少采购到H HH磅干草所需的最少花费。输入输出样例 #1输入 #12 15 3 2 5 3输出 #19说明/提示FJ 可以在第二家公司买3 33包干草共花费9 99美元。代码1优化1二维数组#includebits/stdc.husingnamespacestd;constintN10010,M5000010;intn,V,v,w,f[N][M];intmain(){cinnV;memset(f,0x3f,sizeoff);f[0][0]0;for(inti1;in;i){cinvw;for(intj0;jV;j)f[i][j]min(f[i-1][j],f[i][max(0,j-v)]w);}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintM5000010;intn,V,v,w,f[M];intmain(){cinnV;memset(f,0x3f,sizeoff);f[0]0;for(inti1;in;i){cinvw;for(intj0;jV;j)f[j]min(f[j],f[max(0,j-v)]w);}coutf[V];return0;}结果