// // see problem statement at the bottom // // i'll probably should take this down soon since the problem statement // is copyright topcoder yadda yadda yadda // #include #include #include #include enum { N = 50, M = 50 }; using namespace std; int penalty(const string& p, int s, int e) { char seen[26] = {0}; int d = 0; for (int i = s; i <= e; i++) { if (!seen[p[i] - 'a']) { seen[p[i] - 'a'] = 1; ++d; } } return (d - 1)*(d - 1); } // // recursive, exponential, top-down solution // DON'T USE THIS // int min_penalty_r(const string& p, int s, int e, int max_cost) { int min_penalty = penalty(p, s, e); if (min_penalty) { for (int i = s + 1; i <= e; i++) { int c = min(i - s, e - i + 1); if (c <= max_cost) { int t = min_penalty_r(p, s, i - 1, max_cost - c) + min_penalty_r(p, i, e, max_cost - c); if (t < min_penalty) min_penalty = t; } } } return min_penalty; } // // bottom-up dynamic programming O(n^4) solution // int min_penalty(const string& p, int max_cost) { static int memo[N][N][M + 1]; int l = p.size(); for (int d = 0; d < l; d++) { for (int s = 0; s < l - d; s++) { int e = s + d; for (int mc = 0; mc <= max_cost; mc++) { int min_penalty = penalty(p, s, e); if (min_penalty) { for (int k = s + 1; k <= e; k++) { int c = min(k - s, e - k + 1); if (c <= mc) { int t = memo[s][k - 1] [mc - c] + memo[k][e][mc - c]; if (t < min_penalty) min_penalty = t; } } } memo[s][e][mc] = min_penalty; } } } return memo[0][l - 1][max_cost]; } class StringCutter { public: int minPenalty(const string& str, int max_cost); }; int StringCutter::minPenalty(const string& str, int max_cost) { // return min_penalty_r(str, 0, str.size() - 1, max_cost); return min_penalty(str, max_cost); } int main() { StringCutter sc; printf("%d\n", sc.minPenalty("abcdefghgfedcba", 1)); printf("%d\n", sc.minPenalty("aaabbacc", 2)); } /*---------------------------------------------------------------------------- Problem Statement You are given a string s on which you must perform a series of cuts. Your ideal goal is for each of the resulting parts to consist of only equal letters. For example, you would want to cut the string "aaabbacc" into four parts: "aaa" + "bb" + a" + "cc". However, cutting is a costly operation, and you are not allowed to exceed a total cost of maxCost. A single cut separates a string into two parts (left and right). The cost of such a cut is the string length of the shorter part. You must perform the cuts in such a way that minimizes the total penalty of the resulting parts. The penalty of a single part is equal to D squared, where D is the number of distinct letters contained in that part minus 1. For example, if you cut "aaabbacc" into "aaab" + "bacc", the total penalty would be (2-1)^2 + (3-1)^2 = 5. Return the minimum possible penalty you can achieve while not exceeding a total cost of maxCost. Definition Class: StringCutter Method: minPenalty Parameters: string, int Returns: int Method signature: int minPenalty(string s, int maxCost) (be sure your method is public) Constraints - s will contain between 1 and 50 characters, inclusive. - s will contain only lowercase letters ('a'-'z'). - maxCost will be between 1 and 50, inclusive. Examples 0) "aaabbacc" 2 Returns: 1 One way to get the smallest penalty is to make one cut that separates the last 2 characters from the rest of the string. 1) "aabbbbcc" 4 Returns: 0 2) "abcdefgh" 6 Returns: 1 3) "abcdefghgfedcba" 1 Returns: 49 4) "aaaaabbbbbcccc" 4 Returns: 1 */