最新NOIP初赛复习14基本算法思想总结

NOIP初赛复14基算法思想
程序包含两方面描述：数组织描述数类型数组织形式（例数组）称作数结构程序操作流程描述程序操作步骤谓算法正著名计算机科学家沃思（Nikiklaus Wirth）提出公式：数结构+算法程序
算法广义讲解决问题方法程然语言伪代码流程图等种方法描述果程序喻成具生命数结构躯体算法灵魂

枚举
枚举法称穷举法称暴力破解法种针密码破译方法密码进行逐推算直找出真正密码止
基思想：解空间中穷举出种解解进行判断中问题答案然枚举法质属搜索策略面讲回溯法宽度优先搜索总说枚举通列举性进行判断检查
适条件：
1预先确定状态元素数n
2预先确定状态元素a1a2…an值域
注意事项：枚举思想解决实际问题关键步骤划定问题解空间该解空间中枚举解里两点需注意解空间划定必须保证覆盖问题全部解果解空间集合H表示问题解集h表示时枚举法求解二解空间集合问题解集定离散集合说集合中元素列限
常见类型：枚举排列枚举子集
常见方法： 递枚举种方法更直观递推（循环）枚举种方法写起更简洁
优点：枚举算法般现实问题直译建立考察量状态甚穷举状态基础较直观易理解算法正确性较容易证明
缺点：枚举算法效率取决枚举状态数量单状态枚举代价效率较低某情况通利题目特点相部分情况列举提高枚举效率
算法优化：
1    提取效信息
2    减少重复计算
3    原问题化更问题
4    根问题性质进行截枝
5    引进算法
例：NOIP2016玩具谜题NOIP2014生活爆炸版石头剪刀布等

递推
递推种干步重复简运算（规律）描述复杂问题方法定数序列H0H1…Hn…存整数n0n>n0时等号(号号)Hn前面某项Hi(0
基思想：递推定规律计算序列中项通常通计算机前面项出序列中指定项值复杂庞计算程转化简单程次重复该算法利计算机速度快知疲倦机器特点
步骤：建立递推关系式确定边界条件递推求解
应分类：般递推问题组合计数类问题类博弈问题求解动态规划问题递推关系
动态规划递推关系

1般递推边界条件明显动态规划边界条件较隐蔽容易忽视
2般递推数学性较强动态规划数学性相较弱
3般递推划分阶段动态规划般较明显阶段
五种典型递推关系
1Fibonacci数列
递推关系中Fibonacci数列应该家熟悉基础程序设计语言Logo语言中类题目较复杂BasicPascalC语言中Fibonacci数列类题目解法相容易逐渐退出竞赛舞台等说Fibonacci数列没研究价值恰恰相反类题目定启发
Fibonacci数列代表问题意利著名数学家Fibonacci1202年提出兔子繁殖问题(称Fibonacci问题)
问题提出：雌雄兔子假定两月便繁殖雌雄兔子问n月少兔子？
解：设满x月兔子Fx中月新生兔子数目Nx第x1月留兔子数目设Fx1：
FxNx+Fx1
NxFx2  (第x2月兔子第x月繁殖力)
∴FxFx1+Fx2  边界条件：F00F11
面递推关系次
F2F1+F01F3F2+F12F4F3+F23F5F4+F35……
Fabonacci数列常出现较简单组合计数问题中例前竞赛中出现骨牌覆盖问题优选法中Fibonacci数列处较体现
2Hanoi塔问题
问题提出：Hanoi塔n圆盘三根木柱abc组成开始时n圆盘次套a柱图示

求a柱n圆盘述规移c柱：
1次移圆盘
2圆盘三柱存放
3移动程中允许盘压盘
问n盘子a柱移动c柱总计需移动少盘次？
解：设hnn盘子a柱移c柱需移动盘次显然n1时需a 柱盘子直接移动c柱h11n2时先a柱面盘子移动b柱然盘子a柱移c 柱b柱盘子移c柱记3盘次h23类推a柱n(n2)盘子时总先助c柱面n1盘子移动b柱然a柱面盘子移动c柱助a柱b柱n1盘子移动c柱总移动hn1+1+hn1盘次
∴hn2hn1+1    边界条件：h11
3面分割问题
问题提出：设n条封闭曲线画面两条封闭曲线恰相交两点三条封闭曲线相交点问封闭曲线面分割成区域数

解：设ann条封闭曲线面分割成区域数 图313出：a2a12a3a24a4a36
式子中出anan12(n1)然面式子通观察4幅图出结正确性尚保证面妨试着证明面已n1条曲线面分割成an1区域第n1条曲线曲线相交次会增加区域面已n1条封闭曲线第n条曲线已条闭曲线恰相交两点会两条曲线交点面增加2(n1)区域加已an1区域an1+2(n1)区域题递推关系anan1+2(n1)边界条件a11
4Catalan数
Catalan数首先Euler精确计算凸n边形角三角形剖分数问题时常出现组合计数问题中
问题提出：凸n边形中通相交n边形部角线n边形拆分成干三角形拆分数目hn表示hnCatalan数例五边形五种拆分方案h55求意凸n边形相应hn

NOIP初赛复（三）栈卡特兰数>>>
Catalan数较复杂递推关系尤竞赛时候选手难较短时间里建立起正确递推关系然Catalan数类问题搜索方法完成搜索方法利递推关系方法较起仅效率低编程复杂度陡然提高
5第二类Stirling数
五类典型递推关系中第二类Stirling家熟悉正必先解释什第二类Strling数
定义：n区球放m相盒子中求空盒方案数S(nm)表示称第二类Stirling数
面根定义推导带两参数递推关系——第二类Stirling数
解：设n球分b1b2……bn表示中取出球bnbn放法两种：
1bn独占盒子剩球放m1盒子中方案数S2(n1m1)
2bn球占盒子事先b1b2……bn1n1球放入m盒子中然球bn放入中盒子中方案数mS2(n1m)
综合两种情况出第二类Stirling数定理：
S2(nm)mS2(n1m)+S2(n1m1)   (n>1m1)
边界条件定义2推导出：
S2(n0)0S2(n1)1S2(nn)1S2(nk)0(k>n)     
结：通面五种典型递推关系建立程探讨知递推类题目具体情况具体分析通找某状态前面状态联系建立相应递推关系

递
函数程概念数学结构果定义说明部直接间接出现身引称递者递定义程序设计中程函数直接者间接调称递调中直接调称直接递A调BB调A递做间接递
基思想：
1递助递工作栈实现递递推+回
2递推：问题极推进 程做递推程相压栈
3回：问题逐解决回原问题程做回程相弹栈
注意事项：
1    递程函数里调身
2    递策略时必须明确递结束条件称递出口
优点：采递方法编写问题解决程序具结构清晰读性强等优点递算法设计非递算法设计容易问题身递定义者问题涉数结构递定义者问题解决方法递形式时候采递算法解决
缺点：执行效率低尤边界条件设置情况极陷入死循环者存溢出窘境递实现代价巨栈空间耗费程前递推次程序层实变量（值参变参）局部变量构成工作记录压入工作栈栈顶退出该层递时工作记录栈顶弹出释放部分空间想减少工作记录便节省部分空间例某变参转换全局变量某值参省略程部精简
应分类：
1递定义问题树结构递定义解决树关问题时常常采递方法
2解决搜索问题搜索产生节点成树状结构递方法解决类例子N皇问题全排列哈密顿回路图着色性等搜索问题
3实现分治思想难发现种时间复杂度nlogn排序方法中采递形式分治合排序堆排序快速排序存分治思想分开处理采递实进行分治建树程
4输出动态规划中间程动态规划空间求较高保存中间程输出增加倍空间需求时果采递输出完全需浪费宝贵空间
例 定n（n>1）递方法计算1+2+3+4++(n1)+n
算法分析：题递方法求解原符合递三条件：
1题累加问题：前前次+前项前次计算方法相数s(n)s(n1)+n
2定n限次递调
3结束条件n1s1
参考程序
#include
using namespace std
int fac(int)                    递函数
int main()
{
　　int t
　　cin>>t                   输入t值
　　cout<       计算1t累加输出结果
}
int fac(int n)
{
　　if (n1) return 1
　　return (fac(n1)+n)          调层递
}
运行程序T5时输出结果：S15递调执行程图：（设T3）

递调程实质断调程函数程递调次子程序变量（局部变量变参等）址计算机部特殊理方法——栈（先进出）理旦递调结束计算机便开始根栈中存储址返回子程序变量值进行相应操作

递
递推
适合解决问题
1 问题身递定义者问题涉数结构递定义者问题解决方法递形式
2 需利分治思想解决问题
3 回溯深度优先搜索
4 输出动态规划中间程
1 够递推式计算数学题
2 动态规划（必须递推记忆化搜索）
特点
结构清晰读性强
目性强
速度较快较灵活
思路易想
编码方式
函数中调
迭代（for循环等）
代方法
问题性质改写方法
① 问题根程序身特点栈模拟递调
② 问题改写成递推迭代算法
拓扑关系明显时采记忆化搜索

搜索
搜索某种意义枚举算法种改进通枚举程中断排达情况达优化复杂度效果
常见方法：
1深度优先搜索（DFS）
思想：顶点条路直走果发现目标节点返回节点条路直走底总体说DFS直处理底发现法结果逐步返回寻求出路
算法优化：
1优化剪枝：求优值时前状态优值更优退出展结合剪枝
2行性剪枝：提前判断该状态否行解退出
3记忆化搜索：已搜索状态直接退出
4改变搜索序：起希更决策先进行搜索
5优化搜索策略
6预处理找体搜索翻译
7改写成IDA*算法
2宽度优先搜索（BFS）
思想：首先访问起始节点邻接点然访问较远区域逐步扩范围直找目标节点BFS处理含边权图中求解短路径非常效方法算法重图算法原型Dijkstra单源短路径算法Prim生成树算法采宽度优先搜索类似思想
注意事项：
1生成子结点提供指父亲结点指针解出现时候通逆踪找根结点目标结点条路径然求输出路径没必记父亲
2生成结点前面已产生结点较免出现重复结点浪费时间空间陷入死循环
3果目标结点深度费（：路径长度）成正找第解优解时搜索速度深度搜索快求优解时采宽度优先搜索果结点费深度成正时第次找解定优解
4宽度优先搜索效率赖目标结点位置情况果目标结点深度处较深层时需搜索结点数基指数增长
算法优化：
1判重优化：hash二叉排序树
2双广搜启发式搜索
3改写成A*算法
4二分优化

DFS
BFS
优势
1 较适合回溯类搜索
2 参数传递状态修改恢复较方便
3 顶处理问题
4 记忆化搜索容易实现
5 快达解答树底端
1 解决少步数深度问题
2 问题解解答树根结点
3 启发式搜索BFS中更容易实现
4 立刻停止搜索
缺点
1 递算法容易导致栈溢出
2 时容易输出方案
3 易立结束搜索
1 空间般DFS
2 状态重复排时耗时
3迭代加深搜索
深度优先搜索优点较高效逼解缺点初始递方错误会带严重果宽度优先搜索优点迅速找答案算解缺点解答案较时耗时间空间较综合两算法出现折中方法：迭代加深搜索
思想：通限定界k然允许深度优先搜索搜索k层旦没找效解增界
优点：相深度优先搜索没时间开销部分解决深度优先搜索局限需宽度优先搜索般空间需求
例迷宫问题
图示出N*M迷宫图入口出口
编程序印条迷宫入口出口路径里黑色方块单元表示走通（1表示）白色方块单元表示走（0表示）左右四方走果路输出no way
入口
→
0
1
0
0
0
0
0
0
1


0
0
0
0
1
0
0
0
1


1
0
0
0
0
0
1
1
1


0
0
1
1
0
0
0
0
0
→
出口

0
0
0
0
0
0
0
1
1

算法分析：输出条路径典回溯算法问题例出回溯（深搜）程序宽搜程序
深搜参考程序
#include
using namespace std
intnmdesxdesysouxsouytotstepa[51]b[51]map[51][51]
bool f
int move(int x int yint step)
{
 map[x][y]step     走步作标记步数记
 a[step]x  b[step]y             记路径
  if((xdesx)&&(ydesy))
  {
   f1
  totstepstep
  }
   else
   {
     if((ym)&&(map[x][y+1]0)) move(xy+1step+1)         右
     if((f)&&(xn)&&(map[x+1][y]0))  move(x+1ystep+1)   
     if((f)&&(y1)&&(map[x][y1]0))  move(xy1step+1)   左
     if((f)&&(x1)&&(map[x1][y]0))  move(x1ystep+1)   
   }
}
int main()
{
  int ij
 cin>>n>>m                     n行m列迷宫
  for(i1i   for (j1j   cin>>map[i][j]
  cout< cin>>soux>>souy               入口
 cout< cin>>desx>>desy               出口
  f0      f0表示解f1表示找解
 move(souxsouy1)
  if (f)
  {
    for(i1i    cout<  }
else cout<return 0
}
宽搜参考程序
#include
using namespace std
int u[5]{00101}
   w[5]{01010}
intnmijdesxdesysouxsouyheadtailxya[51]b[51]pre[51]map[51][51]
bool f
int print(int d)
{
  if (pre[d]0)print (pre[d])             递输出路径
 cout<}
int main()
{
  int ij
 cin>>n>>m                        n行m列迷宫
  for(i1i   for (j1j    cin>>map[i][j]
  cout< cin>>soux>>souy                             入口
 cout< cin>>desx>>desy                             出口
  head0
  tail1
  f0
 map[soux][souy]1
 a[tail]soux  b[tail]souypre[tail]0
  while(headtail)                           队列空
  {
   head++
    for(i1i<4i++)                        4方
    {
     xa[head]+u[i]  yb[head]+w[i]
      if((x>0)&&(x0)&&(y     {                                     方走
        tail++
       a[tail]x  b[tail]y  pre[tail]head
       map[x][y]1
       if ((xdesx)&&(ydesy))    
      扩展出结点目标结点
        {
         f1
         print(tail)
         break
        }
      }
    }
    if(f) break
  }
  if (f)cout<  return 0
}
 
输入1：
输出1：
输入2：
输出2：
8   5
1   1 1  1 1
 0   0  0  0  1
1   1 1  0  1
1   0  0  0  1
1   0  0  1 1
1   0  0  0  1
1   1 1  0  1
1   0  0  0  1
2 1
8 4
21
22
23
24
34
44
43
53
63
8 5
1   1 1 1 1
 0   0  0  0 1
1   1 1  0 1
1   0  0  0 1
1   0  0 1 1
1   0  0  0 1
1   1 1 1 1
1   0  0  0 1
2 1
8 4
no way


分治
基思想：较规模问题分成（般2）较规模互相独立原问题相相似子问题子问题分成更子问题……直子问题简单直接求解原问题解子问题解合问题分解成两较问题求解时分治方法称二分法
适条件：
1该问题规模缩定程度容易解决
2该问题分解干规模较相问题该问题具优子结构性质
3利该问题分解出子问题解合该问题解
4该问题分解出子问题相互独立子问题间包含公子子问题
递分治算法思想相伴生类算法中非常频繁应递分治算法思想时设计出代码简洁较高效算法
解题步骤：
1分解解决问题划分成干规模较类问题
2求解子问题划分足够时较简单方法解决
3合原问题求子问题解逐层合构成原问题解
应分类： 二分搜索整数法Strassen矩阵法棋盘覆盖合排序快速排序线性时间选择接点问题循环赛日程表汉诺塔等
例：NOIP2012教室NOIP2013转圈游戏等
例递算法实现二分查找：n已排序数输入数m二分查找算法判断否n数中
#include
using namespace std
int jc(intint)
int na[1000]m
int main()
{
  intxyi 
 cin>>n
  x1yn
  for(i1i  cin>>a[i]
 cin>>m                                输入查找数
 jc(xy)                                 递程
 cout<}
int jc(int xint y)                           递程
{
   int k
  k(x+y)2                          取中间位置点
   if(a[k]m)
   cout<  找查找数输出结果
   if (x>y)cout<           else
             {
               if (a[k]               if (a[k]>m) jc(xk1)         前半中查找
             }
}

贪心
基思想：贪心称贪婪算法指问题求解程中总做出目前优选择说贪心算法会考虑全局优解会断考虑局部优解种某求优解问题更简单更迅速设计技术较低代码复杂度时间复杂度较优结果求解似值作
贪心算法没固定算法框架算法设计关键贪心策略选择必须注意贪心算法问题整体优解选择贪心策略必须具备效性某状态程会影响前状态前状态关
存题目正解想出贪心原效果情况采取贪心原时取优方案解决相部分需求解优值问题实际会发现通常采动态规划者网络流方法取代贪心算法
适条件：
1通局部贪心选择达问题全局优解运贪心策略解题般说需步步进行次贪心选择次贪心选择原问题变成相似规模更问题步前似佳选择选择仅做次
2原问题优解包含子问题优解问题具优子结构性质面示例背包问题中第次选择单位重量价值货物第子问题优解第二次选择剩货物中单位重量价值货物样第二子问题优解次类推
3次选择贪心标准？正确贪心标准问题优解确定采贪心策略解决问题时意判断贪心标准否正确尤表面似正确贪心标准迷惑出贪心标准应予严格数学证明
解题步骤：
1建立数学模型描述问题
2求解问题分成干子问题
3子问题求解子问题局部优解
4子问题解局部优解合成原解问题解
例：NOIP2012国王游戏NOIP2013积木赛NOIP2015跳石头等
例部分背包问题
定载重量M卡车N种食品食盐白糖米等已知第i种食品拥Wi公斤商品价值Vi元公斤编程确定装货方案装入卡车中物品总价值
算法分析：物品分割成单位块单位块利益越显然总收益越局部优满足全局优贪心法解答方法：先单位块收益进行排列然循环单位块收益取起直取止便优解
非常容易设计出算法：
问题初始化                             读入数
Vi商品排序
　　i1
　　do
　　{ 
　　  if (m0)  break       果卡车满载跳出循环
　　  mmw[i]
　　  if (m>0)                    第i种商品全部装入卡车
　　  else  (m+w[i])  重量物品i装入卡车
　　  ii+1                                 选择种商品
　　}while (m>0&&i解决述问题程中首先根题设条件找贪心选择标准(Vi)标准直接逐步求优解种解题策略称贪心法

 回溯
基思想：包含问题解解空间树中深度优先搜索策略根结点出发深度探索解空间树探索某结点时先判断该结点否包含问题解果包含该结点出发继续探索果该结点包含问题解说明该结点根结点子树定包含问题终解跳该结点根子树系统探索逐层祖先结点回溯程做解空间树剪枝操作果应回溯法求解问题解回溯解空间树树根样根结点子树探索结束果求解问题解探索解空间树时搜索问题解结束
例素数环12020数摆成环求相邻两数素数
算法分析：非常明显道回溯题目1开始空位20种填进数合法：前面数相左边相邻数素数第20数判断第1数否素数
算法流程：
1数初始化  
2递填数：判断第i数填入否合法
A果合法：填数判断否达目标（20已填完）：印结果递填
B果合法：选择种
参考程序
#include
#include
#include
#include
using namespace std
bool b[21]{0}
int total0a[21]{0}
int search(int)                    回溯程
int print()                       输出方案
bool pd(intint)                  判断素数
int main()
{
    search(1)
   cout<}
int search(int t)
{
    int i
    for(i1i<20i++)          20数选
     if(pd(a[t1]i)&&(b[i]))      
 判断前数否构成素数该数否
      {
        a[t]i
        b[i]1
         if(t20) { if (pd(a[20]a[1])) print()}
            else search(t+1)
        b[i]0
      }
}
int print()
{
   total++
  cout<<<<
   for (intj1j<20j++)
    cout<  cout<  }
bool pd(int xint y)
{
    intk2ix+y
    while(k    if(k>sqrt(i)) return 1
       elsereturn 0
}

动态规划
基思想：阶段决策问题中阶段采取决策般说时间空间关决策赖前状态引起状态转移决策序列变化状态中产生出动态含义称种解决阶段决策优化程动态规划方法

基概念：
阶段：求问题程时间空间恰分成干相互联系阶段
状态：表示阶段客观状态某阶段出发位置前阶段终点
效性：果定某阶段状态阶段程发展受阶段前段状态影响阶段确定时整程确定
决策：阶段状态定该状态演变阶段状态种选择(行动)
策略：阶段决策组成序列
优性原理：问题划分成子问题整问题必须优情况时问题必须优问题具备优子结构性质
适条件：
1优子结构果问题优解中包含子问题优解该问题具优子结构称优化原理优子结构理解整体优局部优反定成立
2重叠子问题解决整问题时先解决子问题解决子问题先解决子子问题 ……子子问题相互独立重复重复子子问题称重叠子问题动态规划算法正利种子问题重叠性质子问题解次解保存表中遇相问题时直接查表需重复计算次查表时间常数
3效性原已求状态受未求状态影响
解题步骤：
1判断问题否具优子结构性质具备动态规划
2问题分成干子问题(分阶段)
3建立状态转移方程(递推公式)
4找出边界条件
5设定初始值
6递推求解
状态转移方程构造动态规划程中重步难步数动态规划寻找状态转移方程条十分高效通道寻找变化中变量（已求值）
例：背包型动态规划：POJ10141068序列型动态规划：POJ 104415763027区间型动态规划：POJ 104811541166棋盘性动态规划：POJ 1010116912191220划分型动态规划：POJ 101710391040树型动态规划：POJ 11631380等
例1短路径问题
图出图图中顶点代表城市两城市间条连线代表道路连线数值代表道路长度现想城市A达城市E样走路程短？短路程长度少？

算法分析：AE全程分成四阶段K表示阶段变量第1阶段初始状态A两条供选择支路AB1AB2第2阶段两初始状态B1B2B1三条供选择支路B2两条供选择支路……DK（XIX+1J）表示第K阶段初始状态XI阶段初始状态X+1J路径距离FK（XI）表示第K阶段XI终点E短距离利倒推方法求解AE短距离
具体计算程：
S1： K 4
F4（D1） 3
F4（D2） 4
F4（D3） 3
S2： K 3
F3（C1） MIN{ D3（C1D1）+ F4（D1）D3（C1D2）+ F4（D2）}
        MIN{ 5+36+4 } 8
F3（C2） D3（C2D1）+ F4（D1） 5+3 8
F3（C3） D3（C3D3）+ F4（D3） 8+3 11
F3（C4） D3（C4D3）+ F4（D3） 3+3 6
S3： K 2   
F2（B1） MIN{ D2（B1C1）+ F3（C1）D2（B1C2）+ F3（C2）
D2（B1C3）+ F3(C3)} MIN{ 1+86+83+11} 9
F2（B2） MIN{ D2（B2C2）+ F3（C2）D2（B2C4）+ F3（C4）}
        MIN{ 8+84+6 } 10
S4： K 1
F1（A） MIN{ D1（AB1）+ F2（B1）D1（AB2）+ F2（B2）}
       MIN{ 5+93+10} 13
A点E点全程短路径A→B2→C4→D3→E短路程长度13
程出阶段中求出阶段初始状态终点E短距离逆序倒推程起点A时便全程短路径短距离
例阶段决策问题中阶段采取决策般说阶段关决策赖前状态引起状态转移决策序列变化状态中产生出动态含义称种解决阶段决策优化程动态规划程序设计方法
#include
#include
usingnamespace std
intmain()
{
   long d[5][5][5]f[10][10]
  memset(d42sizeof(d))         
路径通赋值较值判断
   d[1][1][1]5d[1][1][2]3d[2][1][1]1  
通路径赋正常值
   d[2][1][2]6d[2][1][3]3d[2][2][2]8
   d[2][2][4]4d[3][1][1]5d[3][1][2]6
   d[3][2][1]5d[3][3][3]8d[3][4][3]3
   d[4][1][1]3d[4][2][1]4d[4][3][1]3
   for (int i0i<9++i)
    for (int j0j<9++j) f[i][j]10000000
   f[5][1]0
   for (int i4i>1i)
    for (int j1j<4++j)
     for (int k1k<4++k)
       if(f[i][j]>d[i][j][k]+f[i+1][k])    
走非法路径影响答案
          f[i][j]d[i][j][k]+f[i+1][k]
    cout<}
例2混合背包
旅行者V公斤背包现n件物品重量分W1W2Wn价值分C1C2Cn物品取次（01背包）物品取限次（完全背包）物品取次数限（重背包）求解物品装入背包物品费总超背包容量价值总
输入格式
第行：二整数V(背包容量V<200)N(物品数量N<30)
第2N+1行：行三整数WiCiPi前两整数分表示物品重量价值第三整数0说明物品购买数件数字物品购买件数(Pi)
输出格式
仅行数表示总价值
样例输入mixin
104
2  1  0
3  3  1
4  5  4
样例输出mixout
11
样例解释
选第件物品1件第三件物品2件
参考程序
#include
using namespace std
int m n
int w[31] c[31] p[31]
int f[201]
int max(int xint y) { return  x>yxy }
int main(){
   scanf(dd&m&n)
    for (int i 1 i < n i++)
       scanf(ddd&w[i]&c[i]&p[i])
    for (int i 1 i < n i++)
        if (p[i] 0)  {                        完全背包
            for(int j w[i] j < m j++)
               f[j] max(f[j] f[jw[i]]+c[i])
        }
        else {
            for(int j 1 j < p[i] j++)  01背包重背包
               for (int k m k > w[i] k)
                   f[k] max(f[k]f[kw[i]]+c[i])
        }
   printf(df[m])
    return 0
}
解题目标分信息学试题分四类：判定性问题构造性问题计数问题优化问题竞赛中碰优化问题动态规划正解决优化问题力武器动态规划竞赛中位日益提高递推法处理判定性问题计数问题方面利器

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档