题目描述
两头白天鹅生活在一个部分湖面结了冰的湖泊中,湖面的形状为一个长方形,并且被分割成R行C列的小方格,某些方格中结了冰,这样的方格称之为冰格,其余的方格称之为水格。冬天过去了,湖面上的冰渐渐开始溶解了,每一天与水相邻的冰格就将消融而转化为水格。所谓两个方格相邻是指它们在水平或垂直方向有公共边,两个呈对角的方格是不相邻的,下图给出样例数据的演化过程。
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M x N grid (1 <= M <= 15; 1 <= N <= 15) of square tiles, each of which is colored black on one side and white on the other side. As one would guess, when a single white tile is flipped, it changes to black;
FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求,修好后的路面高度应当单调上升或单调下降,也就是说,高度上升与高度下降的路段不能同时出现在修好的路中。 整条路被分成了N段,N个整数A_1, … , A_N (1 <= N <= 2,000)依次描述了每一段路的高度(0 <= A_i <= 1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1, … , B_N,作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同,修路的总支出可以表示为:$ |A_1 - B_1| + |A_2 - B_2| + … + |A_N - B_N| $请你计算一下,FJ在这项工程上的最小支出是多少。FJ向你保证,这个支出不会超过2^31-1。
In a village called Byteville, there are houses connected with N-1 roads. For each pair of houses, there is a unique way to get from one to another. The houses are numbered from 1 to . The house no. 1 belongs to the village administrator Byteasar. As part of enabling modern technologies for rural areas framework, computers have been delivered to Byteasar’s house. Every house is to be supplied with a computer, and it is Byteasar’s task to distribute them. The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers.