做外贸的网站要多少钱,wordpress链接视频,影视采集网站怎么做收录,科技企业网站建设文章目录1. 题目2. 解题2.1 区间DP1. 题目
几块石子 排成一行 #xff0c;每块石子都有一个关联值#xff0c;关联值为整数#xff0c;由数组 stoneValue 给出。
游戏中的每一轮#xff1a;
Alice 会将这行石子分成两个 非空行#xff08;即#xff0c;左侧行和右侧行…
文章目录1. 题目2. 解题2.1 区间DP1. 题目
几块石子 排成一行 每块石子都有一个关联值关联值为整数由数组 stoneValue 给出。
游戏中的每一轮
Alice 会将这行石子分成两个 非空行即左侧行和右侧行 Bob 负责计算每一行的值即此行中所有石子的值的总和。 Bob 会丢弃值最大的行Alice 的得分为剩下那行的值每轮累加。 如果两行的值相等Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只 剩下一块石子 时游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1
输入stoneValue [6,2,3,4,5,5]
输出18
解释在第一轮中Alice 将行划分为 [623][455] 。
左行的值是 11 右行的值是 14 。
Bob 丢弃了右行Alice 的分数现在是 11 。
在第二轮中Alice 将行分成 [6][23] 。
这一次 Bob 扔掉了左行Alice 的分数变成了 1611 5。
最后一轮 Alice 只能将行分成 [2][3] 。
Bob 扔掉右行Alice 的分数现在是 1816 2。
游戏结束因为这行只剩下一块石头了。示例 2
输入stoneValue [7,7,7,7,7,7,7]
输出28示例 3
输入stoneValue [4]
输出0提示
1 stoneValue.length 500
1 stoneValue[i] 10^6来源力扣LeetCode 链接https://leetcode-cn.com/problems/stone-game-v 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 区间DP 时间复杂度O(n3) 有点高需要优化
dp[l][r] 表示区间内可以得到的最高分区间从小往大区间增加了枚举中间分隔点
class Solution {
public:int stoneGameV(vectorint stoneValue) {int n stoneValue.size(), i, l, r, mid, suml, sumr;vectorvectorint dp(n,vectorint(n,0));vectorint sum(stoneValue);for(i 1; i n; i) sum[i] sum[i-1] stoneValue[i];//前缀和for(int len 1; len n; len)//区间长度{for(l 0; l n; l)//左端点{r llen;//右端点if(r n)continue;for(mid l; mid r; mid)//枚举中间节点{suml sum[mid]-(l0 ? 0 : sum[l-1]);sumr sum[r]-sum[mid];if(suml sumr)dp[l][r] max(dp[l][r], dp[mid1][r]sumr);if(suml sumr)dp[l][r] max(dp[l][r], dp[l][mid]suml);}}}return dp[0][n-1];}
};不使用 vector过了
class Solution {
public:int stoneGameV(vectorint stoneValue) {int n stoneValue.size(), i, l, r, mid, suml, sumr;int dp[501][501];memset(dp,0,sizeof dp);int sum[501] {0};sum[0] stoneValue[0];for(i 1; i n; i) sum[i] sum[i-1] stoneValue[i];for(int len 1; len n; len){for(l 0; l n; l){r llen;if(r n)continue;for(mid l; mid r; mid){suml sum[mid]-(l0 ? 0 : sum[l-1]);sumr sum[r]-sum[mid];if(suml sumr)dp[l][r] max(dp[l][r], dp[mid1][r]sumr);if(suml sumr)dp[l][r] max(dp[l][r], dp[l][mid]suml);}}}return dp[0][n-1];}
};1708 ms 10.6 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
