acm编程比赛入门题目集

旅游路线

Time Limit:1000MS Memory Limit:65536K Total Submit:10 Accepted:7

【问题描述】

假如长江沿岸有n个城市，每个城市依次标号（上游到下游次序编）为1，2，3?, n-3, n-2, n-1, n。alg想从长江上游出发，游玩这些城市。其中alg的旅游路线选取原则为： 1.至少要游玩一个城市。

2.不会游玩相邻的两个城市。即相邻的两个城市不会出现在algoo的旅游路线中。例如：当游玩过城市n-k后，就不会考虑在城市n-k+1停下。

现在你的任务是：如果有n个城市，帮助algoo计算有多少种路线可以选择。

【要求】

【数据输入】多组测试数据。每组测试数据一行，为一个数n（1<=n<=100），表示城市的个数。

【数据输出】对每组测试数据，输出algoo总共有多少种路线选择。

【样例输入】 3 4 5

【样例输出】 4 7 12 Hint

数据会好大^_^

当n=4时，有如下几种路线。 1 2 3 4 1--> 3 1--> 4

2--> 4 （1，3城市都不玩，游玩过城市2后再到城市4） 共7种路线。

割钢管

Time Limit:1000MS Memory Limit:65536K Total Submit:7 Accepted:6

【问题描述】

A公司有一台钢管切割机提供钢管加工业务。钢管切割机每次可以将一根钢管按照要求在指定位置切割为2段。每次切割的费用为钢管的长度。

给定一根长度为L的钢管，要求将其在位置l1

【要求】

【数据输入】多组测试数据。

每组数据第1行有2个正整数L和n，L表示钢管的长度，n表示切割次数。第2行有n个正整数，表示切割位置l1

【数据输出】最小切割总费用并换行.

【样例输入】 15 4 3 9 12 14

【样例输出】 33