TopCoder SRM 357 DIV 2

Problem	Check	Points
250	o	210ぐらい
500	o	240ぐらい
1000	-	-

500がとにかく悔やまれる。途中までわけのわからない力技でやろうとしていたが、DPで即終了じゃないか・・・！って気づいたときにはこんな点数になっていた。
1000はみんな苦労してたっぽくて早々に諦めた。レベルが足りない。

Problem 250 MnemonicMemory

It is often helpful to have a mnemonic phrase handy for a math test. For example, the number 25735 can be remembered as "is there anybody out there". If we count the number of characters in every word, we would get the sequence 2, 5, 7, 3, 5, which represents the original number!

Unfortunately for you, your professor likes to make the students memorize random numbers and then test them. To beat the system, your plan is to come up with mnemonic phrases that will represent the numbers you must memorize.

You are given a String number and a String[] dictionary. Return a single space delimited list of words, where each word is an element of dictionary, and no element of dictionary is used more than once. The phrase must contain exactly n words, where n is the number of digits in the number, and the length of the i-th word must be equal to the i-th digit of the number for all i. If more than one phrase is possible, return the one that comes first alphabetically (in other words, if you have several words of the same length, you should use them in alphabetical order).

class MnemonicMemory {
public:
  string getPhrase(string number, vector <string> dictionary) {
	  deque<string> vs[10];

	  for(int i=0 ; i<dictionary.size() ; i++){
		  int a = dictionary[i].size();
		  vs[a].push_back(dictionary[i]);
	  }

	  for(int i=0 ; i<10 ; i++){
		  sort(vs[i].begin(), vs[i].end());
	  }

	  string str;
	  for(int i=0 ; i<number.size() ; i++){
		  int a = number[i]-'0';
		  str += vs[a].front() + " ";
		  vs[a].pop_front();
	  }

	  return str.substr(0,str.size()-1);
  }
};

Problem 500 Hotel

The hotel industry is difficult to thrive in, especially when competing at a resort city like Las Vegas. Marketing is essential and often gets a large part of total revenues. You have a list of cities you can market at, and a good estimate of how many customers you will get for a certain amount of money spent at each city.

You are given int[]s customers and cost. cost[i] is the amount of money required to get customers[i] customers from the i-th city. You are only allowed to spend integer multiples of the cost for any city. For example, if it costs 9 to get 3 customers from a certain city, you can spend 9 to get 3 customer, 18 to get 6 customers, 27 to get 9 customers, but not 3 to get 1 customer, or 12 to get 4 customers. Each city has an unlimited number of potential customers. Return the minimum amount of money required to get at least minCustomers customers.

class Hotel {
public:
  int marketCost(int minCustomers, vector <int> customers, vector <int> cost) {

	  int dp[10000];

	  for(int i=0 ; i<10000 ; i++){
		  dp[i] = 999999;
	  }
	  dp[0] = 0;

	  for(int i=1 ; i<10000 ; i++){
		  for(int j=0 ; j<customers.size() ; j++){
			  int a = customers[j];
			  if(i-a < 0) continue;

			  int k = dp[i-a] + cost[j];

			  dp[i] = min(dp[i], k);

		  }
	  }

	  int minCost = 9999999;
	  for(int i=minCustomers ; i<10000 ; i++){
		  minCost = min(minCost, dp[i]);
	  }
	  return minCost;

  }
};