• A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.

    要求构造只含特定素数(2 3 5 7)的 数。

     

  • http://acm.hdu.edu.cn/showproblem.php?pid=1087

    动态规划着实妙不可言,此题求最大上升子序之和。

    1.设第i个棋子的值为a[i],考虑从起点开始一路跳至第i个棋子的最大上升子序列之和为Sum[i]。

    那么跳到i点的前一步可以是j

    Sum[i]=Max{Sum[j]}+a[i];(其中a[j]

    所以只要建立子问题的最优解,就可以建立原问题的某个示例的最优解。

    2.任意一点都可以直接跳到终点,所以最终解为S*=max{sum[i]};

    Sum[i]=Max{Sum[j]}+a[i];i!=0;

    Sum[0]=0;a[0]=0;起始值设为0;

     

    追踪最大子序的元素(题目不要求):

    设最终求得最大和为Max,自后向前在Sum[i]搜索Sum[i]==M