背包问题九讲
version 1.1 build 20071115
前言
目录
W一?01背包问题
W二?完全背包问题
W三?多重背包问题
W四?混合三种背包问题
W五?二维费用的背包问?
W六?分组的背包问?
W七?有依赖的背包问题
W八?泛化物品
W九?背包问题问法的变?
附录一QUSACO中的背包问题
附录二：背包问题的搜索解?
联系方式
致谢
前言
本篇文章是我(dd_engi)正在q行中的一个雄心勃勃的写作计划的一部分Q这个计划的内容是写作一份较为完善的NOIP隑ֺ的动态规划ȝQ名为《解动态规划题的基本思考方式》。现在你看到的是q个写作计划最先发布的一部分?/p>
背包问题是一个经典的动态规划模型。它既简单Ş象容易理解，又在某种E度上能够揭C动态规划的本质Q故不少教材都把它作为动态规划部分的W一道例题，我也它攑֜我的写作计划的第一部分?/p>
L文最重要的是思考。因为我的语a和写作方式向来不以易于理解ؓ长，思\也偶有蟩跃的地方Q后面更有需要大量思考才能理解的比较抽象的内宏V更重要的是Q不大量思考，l对不可能学好动态规划这一信息学奥赛中最_致的部分?/p>
你现在看到的是本文的v1.1版，发布?007q?1?5日。我会长期维护这份文本，把大家的意见和徏议融入其中，也会不断加入我在OI学习以及来可能的ACM-ICPC的征E中得到的新的心得。但目前本文q没有一个固定的发布面Q想了解本文是否有更新版本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜烦贴子Q每ơ比较重大的版本更新都会在这个论坛里发脓公布。也可以?#8220;背包问题九讲”为关键字在搜索引擎中搜烦以得到最新版本?/p>
目录
W一?01背包问题
q是最基本的背包问题，每个物品最多只能放一ơ?/p>
P01: 01背包问题
题目
有N件物品和一个容量ؓV的背包。第i件物品的费用是c[i]Qh值是w[i]。求解将哪些物品装入背包可价值d最大?/p>
基本思\
q是最基础的背包问题，特点是：每种物品仅有一Ӟ可以选择放或不放?/p>
用子问题定义状态：即f[i][v]表示前i件物品恰攑օ一个容量ؓv的背包可以获得的最大h倹{则其状态{ULE便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
q个方程非常重要Q基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要它详细解释一下：“前i件物品放入容量ؓv的背包中”q个子问题，若只考虑Wi件物品的{略Q放或不放）Q那么就可以转化Z个只牉|前i-1件物品的问题。如果不攄i件物品，那么问题p{化ؓ“前i-1件物品放入容量ؓv的背包中”Qhgؓf[i-1][v]Q如果放Wi件物品，那么问题p{化ؓ“前i-1件物品放入剩下的定w为v-c[i]的背包中”Q此时能获得的最大h值就是f[i-1][v-c[i]]再加上通过攑օWi件物品获得的价值w[i]?/p>
优化I间复杂?br>以上Ҏ的时间和I间复杂度均为O(VN)Q其中时间复杂度应该已经不能再优化了Q但I间复杂度却可以优化到O?/p>
先考虑上面讲的基本思\如何实现Q肯定是有一个主循环i=1..NQ每ơ算出来二维数组f[i][0..V]的所有倹{那么，如果只用一个数lf[0..V]Q能不能保证Wiơ@环结束后f[v]中表C的是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来Q能否保证在推f[i][v]Ӟ也即在第iơ主循环中推f[v]Ӟ能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢Q事实上Q这要求在每ơ主循环中我们以v=V..0的顺序推f[v]Q这h能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的倹{伪代码如下Q?/p>
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰q当于我们的{ULEf[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}Q因为现在的f[v-c[i]]q当于原来的f[i-1][v-c[i]]。如果将v的@环顺序从上面的逆序Ҏ序的话Q那么则成了f[i][v]由f[i][v-c[i]]推知Q与本题意不W，但它却是另一个重要的背包问题P02最L解决ҎQ故学习只用一l数l解01背包问题是十分必要的?/p>
事实上，使用一l数l解01背包的程序在后面会被多次用到Q所以这里抽象出一个处理一?1背包中的物品q程Q以后的代码中直接调用不加说明?/p>
q程ZeroOnePackQ表C处理一?1背包中的物品Q两个参数cost、weight分别表明qg物品的费用和价倹{?/p>
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意q个q程里的处理与前面给出的伪代码有所不同。前面的CZE序写成v=V..0是ؓ了在E序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已l抽象成看作黑箱的过E了Q就可以加入优化。费用ؓcost的物品不会媄响状态f[0..cost-1]Q这是显然的?/p>
有了q个q程以后Q?1背包问题的伪代码可以这样写Q?/p>
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的l节问题
我们看到的求最优解的背包问题题目中Q事实上有两U不太相同的问法。有的题目要?#8220;恰好装满背包”时的最优解Q有的题目则q没有要求必L背包装满。一U区别这两种问法的实现方法是在初始化的时候有所不同?/p>
如果是第一U问法，要求恰好装满背包Q那么在初始化时除了f[0]?其它f[1..V]均设?∞Q这样就可以保证最l得到的f[N]是一U恰好装满背包的最优解?/p>
如果q没有要求必L背包装满Q而是只希望h格尽量大Q初始化时应该将f[0..V]全部设ؓ0?/p>
Z么呢Q可以这L解：初始化的f数组事实上就是在没有M物品可以攑օ背包时的合法状态。如果要求背包恰好装满，那么此时只有定w?的背包可能被价gؓ0的nothing“恰好装满”Q其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包ƈ非必被装满Q那么Q何容量的背包都有一个合法解“什么都不装”Q这个解的hgؓ0Q所以初始时状态的g全部ؓ0了?/p>
q个技巧完全可以推q到其它cd的背包问题，后面也就不再对进行状态{UM前的初始化进行讲解?/p>
一个常C?br>前面的伪代码中有 for v=V..1Q可以将q个循环的下限进行改q?/p>
׃只需要最后f[v]的|倒推前一个物品，其实只要知道f[v-w[n]]卛_。以此类推，对以Wj个背包，其实只需要知道到f[v-sum{w[j..n]}]卛_Q即代码中的
for i=1..N
for v=V..0
可以Ҏ
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
q对于V比较大时是有用的?/p>
结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方E的最基本思想Q另外，别的cd的背包问题往往也可以{换成01背包问题求解。故一定要仔细体会上面基本思\的得出方法，状态{ULE的意义Q以及最后怎样优化的空间复杂度?br>
W二?完全背包问题
W二个基本的背包问题模型Q每U物品可以放无限多次?br>P02: 完全背包问题
题目
有NU物品和一个容量ؓV的背包，每种物品都有无限件可用。第iU物品的费用是c[i]Qh值是w[i]。求解将哪些物品装入背包可ɘq些物品的费用d不超q背包容量，且h值d最大?/p>
基本思\
q个问题非常cM?1背包问题Q所不同的是每种物品有无限g。也是从每U物品的角度考虑Q与它相关的{略已ƈ非取或不取两U，而是有取0件、取1件、取2?#8230;…{很多种。如果仍然按照解01背包时的思\Qof[i][v]表示前iU物品恰攑օ一个容量ؓv的背包的最大权倹{仍然可以按照每U物品不同的{略写出状态{ULE，像这P
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
q跟01背包问题一hO(VN)个状态需要求解，但求解每个状态的旉已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])Qȝ复杂度可以认为是O(V*Σ(V/c[i]))Q是比较大的?/p>
?1背包问题的基本思\加以改进Q得Cq样一个清晰的Ҏ。这说明01背包问题的方E的是很重要，可以推及其它cd的背包问题。但我们q是试图改进q个复杂度?/p>
一个简单有效的优化
完全背包问题有一个很单有效的优化Q是q样的：若两件物品i、j满c[i]<=c[j]且w[i]>=w[j]Q则物品jLQ不用考虑。这个优化的正确性显ӞM情况下都可将价值小费用高得j换成物美价廉的iQ得到至不会更差的Ҏ。对于随机生成的数据Q这个方法往往会大大减物品的件数Q从而加快速度。然而这个ƈ不能改善最坏情늚复杂度，因ؓ有可能特别设计的数据可以一件物品也M掉?/p>
q个优化可以单的O(N^2)地实玎ͼ一般都可以承受。另外，针对背包问题而言Q比较不错的一U方法是Q首先将费用大于V的物品去掉，然后使用cM计数排序的做法，计算用相同的物品中h值最高的是哪个，可以O(V+N)地完成这个优化。这个不太重要的q程׃l出伪代码了Q希望你能独立思考写Z代码或程序?/p>
转化?1背包问题求解
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题{化ؓ01背包问题来解。最单的x是，考虑到第iU物品最多选V/c[i]Ӟ于是可以把第iU物品{化ؓV/c[i]件费用及价值均不变的物品，然后求解q个01背包问题。这样完全没有改q基本思\的时间复杂度Q但q毕竟给了我们将完全背包问题转化?1背包问题的思\Q将一U物品拆成多件物品?/p>
更高效的转化Ҏ是：把第iU物品拆成费用ؓc[i]*2^k、hgؓw[i]*2^k的若qg物品Q其中k满c[i]*2^k<=V。这是二q制的思想Q因Z最优策略选几件第iU物品，d以表C成若干?^k件物品的和。这h每种物品拆成O(log V/c[i])件物品，是一个很大的改进?/p>
但我们有更优的O(VN)的算法?/p>
O(VN)的算?br>q个法使用一l数l，先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现Q这个伪代码与P01的伪代码只有v的@环次序不同而已。ؓ什么这样一改就可行呢？首先xZ么P01中要按照v=V..0的逆序来@环。这是因保证Wiơ@环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话_q正是ؓ了保证每件物品只选一ơ，保证在考虑“选入Wi件物?#8221;qg{略Ӟ依据的是一个绝无已l选入Wi件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限gQ所以在考虑“加选一件第iU物?#8221;q种{略Ӟ却正需要一个可能已选入WiU物品的子结果f[i][v-c[i]]Q所以就可以q且必须采用v=0..V的顺序@环。这是q个单的E序Z成立的道理?/p>
值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常C的优化?/p>
q个法也可以以另外的思\得出。例如，基本思\中求解f[i][v-c[i]]的状态{ULE显式地写出来，代入原方E中Q会发现该方E可以等价地变Ş成这UŞ式：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
这个方E用一l数l实玎ͼ便得C上面的伪代码?/p>
最后抽象出处理一件完全背包类物品的过E伪代码Q?/p>
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
ȝ
完全背包问题也是一个相当基的背包问题，它有两个状态{ULE，分别?#8220;基本思\”以及“O(VN)的算?#8220;的小节中l出。希望你能够对这两个状态{ULE都仔细C会，不仅CQ也要弄明白它们是怎么得出来的Q最好能够自己想一U得到这些方E的Ҏ。事实上Q对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法?/p>
W三?多重背包问题
每种物品有一个固定的ơ数上限?br>P03: 多重背包问题
题目
有NU物品和一个容量ؓV的背包。第iU物品最多有n[i]件可用，每g费用是c[i]Qh值是w[i]。求解将哪些物品装入背包可ɘq些物品的费用d不超q背包容量，且h值d最大?/p>
基本法
q题目和完全背包问题很类伹{基本的方程只需完全背包问题的方程略微一改即可，因ؓ对于WiU物品有n[i]+1U策略：?Ӟ??#8230;…取n[i]件。of[i][v]表示前iU物品恰攑օ一个容量ؓv的背包的最大权|则有状态{ULE：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
复杂度是O(V*Σn[i])?/p>
转化?1背包问题
另一U好惛_写的基本Ҏ是{化ؓ01背包求解Q把WiU物品换成n[i]?1背包中的物品Q则得到了物品数?#931;n[i]?1背包问题Q直接求解，复杂度仍然是O(V*Σn[i])?/p>
但是我们期望它转化?1背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想Q我们考虑把第iU物品换成若qg物品Q得原问题中第iU物品可取的每种{略——取0..n[i]件——均能等价于取若qg代换以后的物品。另外，取超qn[i]件的{略必不能出现?/p>
Ҏ是：第iU物品分成若qg物品Q其中每件物品有一个系敎ͼqg物品的费用和价值均是原来的费用和hg以这个系数。ɘq些pL分别?,2,4,...,2^(k-1),n[i]-2^k+1Q且k是满n[i]-2^k+1>0的最大整数。例如，如果n[i]?3Q就这U物品分成系数分别ؓ1,2,4,6的四件物品?/p>
分成的这几g物品的系数和为n[i]Q表明不可能取多于n[i]件的WiU物品。另外这U方法也能保证对?..n[i]间的每一个整敎ͼ均可以用若干个系数的和表C，q个证明可以?..2^k-1?^k..n[i]两段来分别讨论得出，q不难，希望你自己思考尝试一下?/p>
q样将WiU物品分成了O(log n[i])U物品，原问题转化Z复杂度ؓ<math>O(V*Σlog n[i])?1背包问题Q是很大的改q?/p>
下面l出O(log amount)旉处理一件多重背包中物品的过E，其中amount表示物品的数量：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k<amount
ZeroOnePack(k*cost,k*weight)
amount=amount-k
k=k*2
ZeroOnePack(amount*cost,amount*weight)
希望你仔l体会这个伪代码Q如果不太理解的话，不妨译成程序代码以后，单步执行几次Q或者头脑加U笔模拟一下，也许׃慢慢理解了?/p>
O(VN)的算?br>多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态{ULE，但应用单调队列的Ҏ使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超ZNOIP的范_故本文不再展开讲解。我最初了解到q个Ҏ是在楼天成的“男h八题”qȝ片上?/p>
结
q里我们看到了将一个算法的复杂度由O(V*Σn[i])改进到O(V*Σlog n[i])的过E，q知道了存在应用出NOIP范围的知识的O(VN)法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正性，q将完整的程序代码写出来?/p>
题目如下Q?br>对于?到N的连l整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的?br>举个例子Q如果N=3Q对于{1Q?Q?}能划分成两个子集合，他们每个的所有数字和是相{的Q?br>and {1,2}
q是唯一一U分发（交换集合位置被认为是同一U划分方案，因此不会增加划分ҎLQ?br>如果N=7Q有四种Ҏ能划分集合{1Q?Q?Q?Q?Q?Q?}Q每一U分发的子集合各数字和是相等?
{1,6,7} and {2,3,4,5} {?1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
l出NQ你的程序应该输出划分方案LQ如果不存在q样的划分方案，则输?。程序不能预存结果直接输出?br>PROGRAM NAME: subset
INPUT FORMAT
输入文g只有一行，且只有一个整数N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
输出划分ҎLQ如果不存在则输??br>SAMPLE OUTPUT (file subset.out)
4
参考程序如下：
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
题目如下Q?br>在生物学中，一些生物的l构是用包含其要素的大写字母序列来表C的。生物学家对于把长的序列分解成较短的Q称之ؓ元素的）序列很感兴趣?
如果一个集?P 中的元素可以通过串联Q允讔R复；串联Q相当于 Pascal 中的 “+” q算W）l成一个序?S Q那么我们认为序?S 可以分解?P 中的元素。ƈ不是所有的元素都必d现。D个例子，序列 ABABACABAAB 可以分解Z面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前?K 个字W称?S 中长度ؓ K 的前~。设计一个程序，输入一个元素集合以及一个大写字母序列，计算q个序列最长的前缀的长度?
PROGRAM NAME: prefix
INPUT FORMAT
输入数据的开头包?1..200 个元素（长度?1..10 Q组成的集合Q用q箋的以I格分开的字W串表示。字母全部是大写Q数据可能不止一行。元素集合结束的标志是一个只包含一?“.” 的行。集合中的元素没有重复。接着是大写字母序?S Q长度ؓ 1..200,000 Q用一行或者多行的字符串来表示Q每行不过 76 个字W。换行符q不是序?S 的一部分?br>SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，输出一个整敎ͼ表示 S 能够分解?P 中元素的最长前~的长度?br>SAMPLE OUTPUT (file prefix.out)
11
CZE序如下Q?br>
#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
/* maximum length of a primitive */
#define MAXL 10
char prim[MAXP+1][MAXL+1]; /* primitives */
int nump; /* number of primitives */
int start[200001]; /* is this prefix of the sequence expressible? */
char data[200000]; /* the sequence */
int ndata; /* length of the sequence */
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
/* read in primitives */
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
/* read in string, one line at a time */
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ /* for each expressible prefix */
best = lv; /* we found a longer expressible prefix! */
/* for each primitive, determine the the sequence starting at
this location matches it */
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) /* it matched! */
start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
}
}
/* see if the entire sequence is expressible */
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
题目如下Q?br>我们试着设计我们的竞赛以便h们能可能的多得?q需要你的帮助?br>我们可以从几个种cM选取竞赛的题?q里的一?U类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间ƈ且能得到相同的分数?br>你的d是写一个程序来告诉USACO的职?应该从每一个种cM选取多少题目,使得解决题目的总耗时在竞赛规定的旉里ƈ且d最大?br>输入包括竞赛的时?M(1 <= M <= 10,000)和N,"U类"的数? <= N <= 10,000?br>后面的每一行将包括两个整数来描qC?U类":
W一个整数说明解册U题目能得的分数(1 <= points <= 10000),W二整数说明解决q种题目所需的时?1 <= minutes <= 10000)?br>你的E序应该定我们应该从每?U类"中选多道题目使得能在竞赛的时间中得到最大的分数?br>来自L?U类"的题目数目可能Q何非负数(0或更??br>计算可能得到的最大分数?br>PROGRAM NAME: inflate
INPUT FORMAT
W?1 ? M, N--竞赛的时间和题目"U类"的数目?
W?2-N+1 ? 两个整数:每个"U类"题目的分数和耗时?
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
单独的一行包括那个在l定的限刉可能得到的最大的分数?br>SAMPLE OUTPUT (file inflate.out)
605
{从第2?U类"中选两题，W??U类"中选三题}
CZE序如下Q?br>
#include <fstream.h>
ifstream fin("inflate.in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // ׃数组元素不减Q末元素最?br>}
USACO 3.3
A Game
题目如下Q?br>有如下一个双人游?N(2 <= N <= 100)个正整数的序列放在一个游戏^CQ两从序列的两端取敎ͼ取数后该数字被去掉ƈ累加到本玩家的得分中Q当数取时Q游戏结束。以最l得分多者ؓ胜?
~一个执行最优策略的E序Q最优策略就是自己能得到在当前情况下最大的可能的d的策略。你的程序要始终为第二位玩家执行最优策略?br>PROGRAM NAME: game1
INPUT FORMAT
W一? 正整数N, 表示序列中正整数的个数?
W二行至末尾: 用空格分隔的N个正整数Q大ؓ1-200Q?
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行，用空格分隔的两个整数: 依次为玩家一和玩家二最l的得分?
SAMPLE OUTPUT (file game1.out)
18 11
参考程序如下：
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t = t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
题目如下Q?br>你刚刚得C行?#8220;破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中_N一些歌Ԍ发行M(1 <= M <= 20)张CD。每一张CD最多可以容UT(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中?
不y你是一位古兔R乐迷Q不懂如何判定这些歌的艺术h倹{于是你军_Ҏ以下标准q行选择Q?
歌曲必须按照创作的时间顺序在CD盘上出现?
选中的歌曲数目尽可能地多?
PROGRAM NAME: rockers
INPUT FORMAT
W一行： 三个整数QN, T, M.
W二行： N个整敎ͼ分别表示每首歌的长度Q按创作旉序排列?
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一个整敎ͼ表示可以装进M张CD盘的乐曲的最大数目?
SAMPLE OUTPUT (file rockers.out)
3
参考程序如下：
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)/*当前cd */
for (b = 0; b <= cdlength; b++) /* 已过的时?/
for (c = 0; c <= numsongs; c++) { /* 上一?/
for (d = c + 1; d <= numsongs; d++) { /* 下一?/
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
“逢低吸纳”是炒股的一条成功秘诀。如果你xZ个成功的投资者，p遵守q条U诀:
"逢低吸纳,低买"
q句话的意思是Q每ơ你购买股票时的股h一定要比你上次购买时的股h?按照q个规则购买股票的次数越多越好，看看你最多能按这个规则买几次?br>l定q箋的N天中每天的股仗你可以在Q何一天购Cơ股，但是购买时的股h一定要比你上次购买时的股h低。写一个程序，求出最多能买几ơ股?
以下面这个表Z, 某几天的股h?
天数 1 2 3 4 5 6 7 8 9 10 11 12
股h 68 69 54 64 68 64 70 67 78 62 98 87
q个例子? 聪明的投资?按上面的定义)Q如果每ơ买股票时的股h都比上一ơ买时低Q那么他最多能?ơ股。一U买法如?可能有其他的买法):
天数 2 5 6 10
股h 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
W?? N (1 <= N <= 5000), 表示能买股票的天数?
W?行以? N个正整数 (可能分多? Q第i个正整数表示Wi天的股h. q些正整数大不会超qlongint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行，输出两个整数Q?
能够买进股票的天?
长度辑ֈq个值的股票购买Ҏ数量
在计解的数量的时候，如果两个解所l成的字W串相同Q那么这L两个解被认ؓ是相同的Q只能算做一个解Q。因此，两个不同的购买方案可能生同一个字W串Q这样只能计一ơ?
SAMPLE OUTPUT (file buylow.out)
4 2
参考程序如下：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
/*初始化高_ֺ?/
void init_big(bignum_t *num, int val)
{
*num = get_big();
/* initialize */
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; /* carry */
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
/* if a->val is too large, we need to carry */
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ /* allocate if we need to */
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
/* 用DP计算最大长?/
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
/* 找最长串*/
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
/* output answer */
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}