解题记录 1
Published:
Largest Sum of Averages
问题描述
- 将数组A分成K个相邻的组，使得每个组的平均值的和最大
想法
f[i][k] = max(f[j][k-1] + (sum[i] - sum[j])/(i - j), f[n][k]]), k-1<= j <= i-1- 当前第i个数组元素分成k个组的值是由第j个元素k-1个组加上i到j之间数字的平均值和当前值比较取max得到的
- 一开始想法已经差不多对了，递推式很快就出来了，但是有一些实现上的细节问题。比如因为要计算平均值，所以要记录和。这个和可以预先处理好，因为区间和可以两端相减得到。同时
f[i][1]的值也有了。 - 为了避免思维复杂，所有的下标都从1开始。比如sum[1]就是第一个数的值。i, j, k都从1开始。注意，因为
f[i][1]已经预处理了，所以真正循环的时候要从k=2开始。 - 为了提高效率，还要特判一下两个特殊条件，一个是K=n（返回所有的和）, 一个是K=1 （返回平均值）。
代码
public double largestSumOfAverages(int[] A, int K) { int n = A.length; int[] sums = new int[A.length + 1]; for (int i = 0; i < n; i++) { sums[i + 1] = sums[i] + A[i]; } // special case if (K <= 1) return 1.0 * sums[n] / n; if (K >= n) return sums[n]; double[][] f = new double[n + 1][K + 1]; for (int i = 1; i <= n; i++) { f[i][1] = (1.0 * sums[i]) / i; } for (int k = 2; k <= K; k++) { for (int i = k; i <= n; i++) { for (int j = i - 1; j >= k - 1; j--) { f[i][k] = Math.max(f[i][k], f[j][k - 1] + (sums[i] - sums[j]) * 1.0 / (i - j)); } } } return f[n][K]; }
Soup servings
问题描述
有A,B两桶汤。有四种serve的方式
- Serve 100 ml of soup A and 0 ml of soup B
- Serve 75 ml of soup A and 25 ml of soup B
- Serve 50 ml of soup A and 50 ml of soup B
- Serve 25 ml of soup A and 75 ml of soup B
已知选取每种方式的可能性为0.25。如果剩余的汤不够的话就把里面所有的汤都serve出来。当某种汤没了就停止。试问汤的量为N的时候A先空的概率与一半两者同时空的概率的和。
想法
首先一点，所有的serving都是25的整数倍，可以先normalize一下（重要：数据处理基本），也就是除以25。当前汤状态
f[i][j]可以从一下几个状态转移而来f[i][j] = (f[i+4][j]+ f[i+3][j+1] + f[i+2][j+2] + f[i+1][j+3])* 0.25换言之，
f[i][j]也可以0.25的概率转移到相应更小的状态。其次，有一个显而易见的规律，如果每次都选前两种方式，A必然先选完。但是这个规律不够general，对解题帮助不大。因为我们还要考虑两者同时选完的情况。
原题中N的数据范围直到十的九次方，所以下标势必会很大，如果用普通状态记录方式必然不得行。
最后还是看了discussion，发现当N>=4800的情况下概率将接近1，返回1即可，剩下的情况有人使用记忆化递归解决，但实际上一般的DP应该也可以，只是初始情况比较难处理（起始条件比较多），而递归好处理一些。
代码
double[][] f = new double[200][200]; public double dfs(int a, int b) { // go out at the same time if (a <= 0 && b <= 0) { return 0.5; } if (a <= 0) { return 1; } if (b <= 0) { return 0; } if (f[a][b] > 0) { return f[a][b]; } double sum = dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3); f[a][b] = 0.25 * sum; return f[a][b]; } public double soupServings(int N) { // got this number from discussion, or N will be too big to calculate; if (N >= 4800) return 1.0; int a = (N + 24) / 25; return dfs(a, a); }
Ones and Zeroes
问题描述
现有m个0和n个1。有一些array，每个都有一定数量的0和1。每个0和1能使用仅一次，问能最多能用这m个0和n个1组成这些array中的多少个。
想法
- 刚开始还sort之后想用贪心解决，但是这个问题其实就是一个背包问题的变种。因为这有两个参数：零和一的数量，且每个array的0和1的相对关系不同，所以sort之后并不一定能得到最优解。
- 这里每个array的0和1就是两种cost，这个背包针对两种cost都有限额。目标是要装的越多越好，且不一定能完全装满。
- 这个其实也是一种0-1背包问题，每个array有放入或不放的选项，只不过现在变成了一个二维的问题。
- 对于
f[i][j][k]，实则是从f[i-1][l][r] + 1, cost[i].m=<l<=m,cost[i].n<=r<=n或者自己本身转移而来 - 类似于0-1背包问题，我们也可以舍弃i的哪一维。为了保证
f[i]是从f[i-1]转移而来，采用逆序更新。
- 对于
代码
public int findMaxForm(String[] strs, int m, int n) { int[][] f = new int[m + 1][n + 1]; for (String s: strs) { int mc = 0, nc = 0; // cost[i].m, cost[i].n for (int j = 0; j < s.length(); j++) { if (s.charAt(j) == '0') mc++; else nc++; } for (int i = m; i >= mc; i--) { for (int j = n; j >= nc; j--) { int mr = i - mc; // i - cost[i].m int nr = j - nc; // j - cost[i].n f[i][j] = Math.max(1 + f[mr][nr], f[i][j]); } } } return f[m][n]; }
Max Sum of Rectangles no Larger than K
问题描述
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.
想法
跟最大子矩阵问题差不多，最简单的想法就是预处理面积（跟预处理和差不多）枚举端点，然后计算面积（容斥）最后搞一个max来记录no larger than K的最大值。
原始代码
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { if (matrix.empty()) return 0; int n = matrix.size(), m = matrix[0].size(), res = INT_MIN; int areas[n][m]; memset(areas, 0, sizeof(areas)); for (int i = 0; i < n; i++) { for (int j = 0; j < m;j++) { int area = matrix[i][j]; if (i - 1 >= 0) area += areas[i - 1][j]; if (j - 1 >= 0) area += areas[i][j - 1]; if (i - 1 >= 0 && j - 1 >= 0) area -= areas[i - 1][j - 1]; areas[i][j] = area; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int t = i; t < n; t++) { for (int l = j; l < m; l++) { int area = areas[t][l]; if (i - 1 >= 0) area -= areas[i - 1][l]; if (j - 1 >= 0) area -= areas[t][j - 1]; if (i - 1 >= 0 && j - 1 >= 0) area += areas[i - 1][j - 1]; if (area <= k) res= max(res, area); } } } } return res; }
改进
先看另一个问题
Maximal Rectangle
找最大子矩阵，只不过这里只有零和一
思路
因为一个矩阵是由宽度和高度决定的，所以可以从记录面积转而记录左右，和高度。
所以现在我们记录
left, right, height, left[j]初始成0， right[j]初始成宽度(不减1）。height[j]为0。left[j] = max(left[j], cur_left) 当
matrix[i][j]==1, 否则记录cur_left = j + 1;(从左到右)right[j] = min(right[j], cur_right) 当
matrix[i][j] ==1，否则记录cur_right=j（包含末尾，这样算长度的时候不用加1）;（从右到左）height[j]，如果
matrix[i][j] ==1, height[j]++最后循环一遍j每个矩阵的面积就是
(right[j]-left[j])* height[j]解释：left[j]表示这一行里面第j列的数字所在的矩阵的左边开始坐标，right， height以此类推
如果不为0，1那么可以做一下转化
先看一个一维数组，现在要求这个数组里面的最大subarray
这个问题可以转化为选择从当前这个数开始计算sum，或者继续之前算好的sum算。那么可以写出
f[i] = max(f[i - 1] + a[i], 0 + a[i])left[j]初始成0， right[j]初始成宽度(不减1)
如果重新开始计数，left[j] = j, right[j - 1] = j
否则left[j - 1] = left[j];
right[n - 1] = n, 从n - 2 开始反着更新一遍，
right[j] = min(right[j + 1]， right[j]);高度处理：对每一列的高度，
height[j] = max(height[j - 1] + mat[i][j], mat[i][j]);
这种方法可以用来定位矩阵，如果只要求值的话，那么可以记录每一列对应高度的和
f[i][j]然后枚举从i到m的各个高度组合, 再用一位数组求最大subarray的方法求，代码如下。代码
int max_rect(vector<vector<int>> mat) { int maxn = 0; int m = mat.size(), n = mat[0].size(); vector<vector<int>> f(m + 1, vector<int>(n + 1, 0)); vector<int> g(n + 1, 0); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { f[i][j] = f[i - 1][j] + mat[i - 1][j - 1]; } } for (int i = 0; i < m; i++) { for (int j = i + 1; j <= m; j++) { for (int k = 1; k <= n; k++) { g[k] = f[j][k] - f[i][k]; } int sum = 0; // O(n) find max sum for (int j = 1; j <= n; j++) { if (sum + g[j] < g[j]) { sum = g[j]; } else { sum += g[j]; } } maxn = max(sum, maxn); } } return maxn; }
以上的那个题目也可以用类似的方法解决。
但是因为这个题目有最大和的限制，所以之前的解法并不能涵盖这个情况，会导致要把所有的起始结尾组合的sum都要算一遍，就变回了O(n * n)
- 所以对于这种有大小限制的，可以另见一个set或者有序队列，每次进入一个sum，并在set中二分查找有无刚好比（sum - k) 大的前缀和，结果就是现在的sum减去这个前缀和。这个优化非常像最长上升子序列的优化一般。
int sum = 0; set<int> s; for(int j = 1; j <= n; j++) { sum += g[j]; auto it = s.lower_bound(sum - k); if(it != s.end()) res = max(res, sum - *it); s.insert(sum); }