• DAG上的的动态规划(DP)
  • 拓扑排序
DAG
DAG
  • 嵌套矩形问题:有n个矩形,每个矩形可以用两个整数a、b描 述,表示它的长和宽。矩形X(a,b)可以嵌套在Y(c,d)中,当且 仅当a<c,b<d,或者b<c,a<d(相当于把矩形X旋转90°)。
  • 硬币问题:有n种硬币,面值分别为V1,V2,…,Vn,每种都有无 限多。给定非负整数S,可以选用多少个硬币,使得面值之和 恰好为S?输出硬币数目的最小值和最大值。 1<=n<=100,0<=S<=10000,1<=Vi<=S。