难度：省选/NOI-

题目描述

        给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

        第一次不看任何解析A出的省选难度题，留作纪念。

难度：省选/NOI-

题目描述

        这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！

难度：提高+/省选-

题目描述

        小新正在玩一个简单的电脑游戏。
        游戏中有一条环形马路，马路上有n个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n个机器人工厂编号为1~n，因为马路是环形的，所以第 n个机器人工厂和第1个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这n段马路也编号为1~n，并规定第i段马路连接第i个机器人工厂和第i+1个机器人工厂（1≤i≤n-1），第n段马路连接第n个机器人工厂和第1个机器人工厂。

难度：提高+/省选-

题目描述

        上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
        THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

        很不容易独立A出的一道题，做做纪念。

难度：提高+/省选-

题目描述

        某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
        从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
        现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
        写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

        给定一棵树，约定选定一个点，被选点可以覆盖与其距离不大于k的所有节点，问覆盖整棵树的最小选点数。
        上一篇《动态规划与状态设计》中提及了k=2的DP做法，但是随着k的增大，状态数也会随之增多，这里介绍一种贪心方法。

        这一篇文章谈谈动态规划(Dynamic Programming， DP)。本材料中大量地出现动态规划类题目，这里做一个总结。
        动态规划是一种解决多阶段决策问题的高效算法设计思路，它的本质是分治思想。对于一个问题，它通常由若干子问题组成，解决了这些子问题，原问题也迎刃而解。例如树这种数据结构，它的分枝仍是一棵树，又如将区间分割，得到的仍是一个区间…很多事物都满足这种性质，可以考虑用DP思路解决。

难度：提高+/省选-

题目背景

        小a和uim来到雨林中探险。突然一阵北风吹来，一片乌云从北部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个披头散发，青面獠牙的怪物，低沉着声音说：“呵呵，既然你们来到这，只能活下来一个！”。小a和他的小伙伴都惊呆了！

难度：提高+/省选-

题目描述

        对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
        在可以选择的课程中，有2n节课程安排在n个时间段上。在第i(1≤i≤n)个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室c_i上课，而另一节课程在教室d_i进行。
        在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室，则需要提出申请。若申请通过，学生就可以在第i个时间段去教室d_i上课，否则仍然在教室c_i上课。
        由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第i节课程的教室时，申请被通过的概率是一个已知的实数k_i，并且对于不同课程的申请，被通过的概率是互相独立的。

难度：提高+/省选-

题目描述

        设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A，B，C，这个状态称为初始状态。
        现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
        移动时有如下要求:

• 一次只能移一个盘;
• 不允许把大盘移到小盘上面。