杭州品牌网站开发,营销型网站的价格,印章在线制作网站,三网合一网站建设全包费用文章目录1. 题目2. 解题2.1 动态规划1. 题目
n 个桶中小球的个数已知, 可以操作 k 次(每次从桶中取出一个球,或者添加一个球), 每个桶有规定的最大容量 W[i]。 求操作后两相邻桶之间的最大差值的平方的最小值。
n 100
W[i] 100样例 1:
输入:
5
6
[1,2,3,4,5]
[15,…
文章目录1. 题目2. 解题2.1 动态规划1. 题目
n 个桶中小球的个数已知, 可以操作 k 次(每次从桶中取出一个球,或者添加一个球), 每个桶有规定的最大容量 W[i]。 求操作后两相邻桶之间的最大差值的平方的最小值。
n 100
W[i] 100样例 1:
输入:
5
6
[1,2,3,4,5]
[15,15,15,15,15]
说明
共有5个桶最多操作6次
桶内的小球分别是1,2,3,4,5
桶的最大容量分别是15,15,15,15,15。输出:
0https://tianchi.aliyun.com/oj/245809026182441523/267721733892674230
2. 解题
2.1 动态规划
dp[i][k][w] 表示遍历到 i 号桶共操作了 k 次i 号桶的重量为 w 时的 相邻最大差值的平方的最小值时间复杂度较高O(nmax(W[i])k2)O(n\max(W[i])k^2)O(nmax(W[i])k2)侥幸过了
class Solution {
public:/*** param n: the number of buckets* param k: the maximum times of operations* param A: the number of balls in each bucket* param W: the maximum capacity of each bucket* return: return the minimum square value of the maximum difference*/int getAns(int n, int k, vectorint A, vectorint W) {// write your code herevectorvectorvectorint dp(n, vectorvectorint(k1, vectorint(101, INT_MAX)));for(int ki 0; ki k; ki){ // 初始化if(A[0]-ki 0)//减少球dp[0][ki][A[0]-ki] 0;//边界if(A[0]ki W[0])//增加球dp[0][ki][A[0]ki] 0;}for(int i 1; i n; i){ //遍历样本for(int k1 0; k1 k; k1){ //到前一个位置为止共操作了 k1 次for(int w1 0; w1 W[i-1]; w1){ //前一个位置 的重量 w1if(dp[i-1][k1][w1] INT_MAX)continue;for(int k2 0; k2k1 k; k2){ // 当前位置的操作次数 k2, 总次数 k1k2 不能超if(A[i]-k2 0)//拿走一些dp[i][k2k1][A[i]-k2] min(dp[i][k2k1][A[i]-k2], max(dp[i-1][k1][w1], (w1-A[i]k2)*(w1-A[i]k2)));if(A[i]k2 W[i])//放进去一些dp[i][k2k1][A[i]k2] min(dp[i][k2k1][A[i]k2], max(dp[i-1][k1][w1], (w1-A[i]-k2)*(w1-A[i]-k2)));}}}}int ans INT_MAX;for(int ki 0; ki k; ki){for(int wi 0; wi W[n-1]; wi)ans min(ans, dp[n-1][ki][wi]);}return ans;}
};401ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
