TopCoder SRM#667(Div2)(2/3)

maksyuki 发表于 比赛 分类,标签:

A Problem Statement

You are given two distinct points A and B in the two-dimensional plane. Your task is to find any point C with the following properties:

C is different from A and B.
Each coordinate of C is an integer between -100 and 100, inclusive.The distance between A and C is strictly greater than the distance between B and C.You are given four ints: x1, y1, x2, and y2. Point A has coordinates (x1,y1) and point B has coordinates (x2,y2). Find the coordinates (x3,y3) of one possible point C with the above properties. Return these coordinates as a vector <int> with two elements: element 0 is x3 and element 1 is y3. In other words, return the vector <int> {x3,y3}.For the constraints given below it is guaranteed that a valid point C always exists. If there are multiple solutions, return any of them.

Class: PointDistance
Method: findPoint
Parameters: int, int, int, int
Returns: vector <int>
Method signature: vector <int> findPoint(int x1, int y1, int x2, int y2)
(be sure your method is public)





B Problem Statement

Cat Noku has just finished writing his first computer program. Noku's computer has m memory cells. The cells have addresses 0 through m-1. Noku's program consists of n instructions. The instructions have mutually independent effects and therefore they may be executed in any order. The instructions must be executed sequentially (i.e., one after another) and each instruction must be executed exactly once.

You are given a description of the n instructions as a vector <string> with n elements. Each instruction is a string of m characters. For each i, character i of an instruction is '1' if this instruction accesses memory cell i, or '0' if it does not.

Noku's computer uses caching, which influences the time needed to execute an instruction. More precisely, executing an instruction takes k^2 units of time, where k is the number of new memory cells this instruction accesses. (I.e., k is the number of memory cells that are accessed by this instruction but have not been accessed by any previously executed instruction. Note that k may be zero, in which case the current instruction is indeed executed in 0 units of time.)

Noku's instructions can be executed in many different orders. Clearly, different orders may lead to a different total time of execution. Find and return the shortest amount of time in which it is possible to execute all instructions.

Class: OrderOfOperationsDiv2
Method: minTime
Parameters: vector <string>
Returns: int
Method signature: int minTime(vector <string> s)
(be sure your method is public)


算法分析:dp[i]表示状态为i时的最小运行时间,初始化i != 0, dp[i] = INF,dp[0] = 0。状态转移方程为dp[i|one_instruction] = min (dp[i|one_instruction], dp[i] + differ(i and one_instruction) ^ 2)。最后输出dp[final_state]即可