Topcoder SRM 610


Div. 2 250 – DivideByZero

题意

给出一个数列,每次可以任意选取数列中的两个数,将较大数整除较小数得到的结果加入数列(重复的不加入),询问数列中最后会有多少数。

分析

由于数最多只有 \(100\) 个,我们可以每次对于当前已经有的数,两两枚举将所有新产生的数全部加入当前数列。

不断进行这个操作,直到没有新的数加入。

这样每次至少会有一个新的数加入,最坏情况下的时间复杂度是 \(O(n^3)\) 。

Div. 2 550 TheMatrix

题意

找一个最大的子矩阵,满足这个子矩阵是一个 \(0/1\) 间隔的矩阵。

分析

由于矩阵最大只有 \(100\times 100\) ,所以可以直接枚举左上角。

对于接下来的每一行,可以取的面积显然就是每一行间隔的 \(0/1\) 长度的 min 。

直接暴力枚举每一行可以取的最大程度,计算面积即可。

 

Div. 2 1000 MiningGoldEasy

题意

每一天都会在一个位置出现黄金,你每一天能够获得的价值是 \(n+m+\) 你所在位置和黄金出现位置的曼哈顿距离。

每一天你可以任意地走到当前所在行的任意位置或者当前所在列的任意位置。

求能够获得的最大价值。

分析

很显然。你所在的位置一定是某一个黄金出现位置的行和某一个黄金出现位置的列(不然只会使得价值变小而没有其他意义)。

于是,我们可以用黄金所在的行和列去重以后的标号来表示当前的位置。

状态 \(f[i][j][k]\) 表示当前是第 \(i\) 天,所在的位置是 \(x[j]\) 行, \(y[j]\) 列。

\(x[i]\) 和 \(y[j]\) 是去重以后的行和列。

每一天首先转移黄金出现后的价值变化。

然后每一个位置可以变为所在行中的最大值或者所在列的最大值(相当于可以在行和列上移动)。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 75,675

Categories

Archive

Comments