题意
给10个杆子和3种环，问套了三种颜色环的杆子有多少
思路
按题意模拟，10个set解决，同时注意给定字符串长度是
2
n
2n
2n。
代码
class Solution {
public:
int countPoints(string rings) {
set ans[10];
int n=rings.size();
for(int i=0;2*i
Problem B - 子数组范围和(https://leetcode-cn.com/problems/sum-of-subarray-ranges/)
题意
求所有连续子数组的"最大值-最小值"之和。
思路
按题意模拟，dp[0][i][j]和dp[1][i][j]分别表示i~j这段子数组的最大值和最小值。
显然有
d
p
[
0
]
[
i
]
[
i
−
j
]
=
m
i
n
(
d
p
[
0
]
[
i
−
1
]
[
i
−
j
]
,
d
p
[
0
]
[
i
]
[
i
−
j
+
1
]
)
;
d
p
[
1
]
[
i
]
[
i
−
j
]
=
m
a
x
(
d
p
[
1
]
[
i
−
1
]
[
i
−
j
]
,
d
p
[
1
]
[
i
]
[
i
−
j
+
1
]
)
;
dp[0][i][i-j]=min(dp[0][i-1][i-j],dp[0][i][i-j+1]);\ dp[1][i][i-j]=max(dp[1][i-1][i-j],dp[1][i][i-j+1]);
dp[0][i][i−j]=min(dp[0][i−1][i−j],dp[0][i][i−j+1]);dp[1][i][i−j]=max(dp[1][i−1][i−j],dp[1][i][i−j+1]);
由此便可
O
(
n
2
)
O(n^2)
O(n2)地解决该问题
代码
class Solution {
public:
long long subArrayRanges(vector& nums) {
int n=nums.size();
long long dp[2][n][n],ans=0;
for(int i=0;i
Problem C - 给植物浇水 II
题意
两个人分别从左边右边同时给n棵植物浇水，每人壶的最大容量为A和B，如果不能完全浇灌下一个植物，就要一直加水直至能够完全浇灌为止，如果两人此刻同时浇灌一颗植物，谁剩的水多谁浇，如果剩的一样多A浇，问总共加水多少次。
思路
按题意模拟，答案显然，注意处理遇见同一颗植物的分类讨论。
代码
class Solution {
public:
int minimumRefill(vector& p, int a, int b) {
int ans=0,n=p.size();
int l=0,r=n-1;
int A=a,B=b;
while(l<=r){
if(l==r){
if(a>=b){
while(a
Problem D - 摘水果
题意
给定数轴上的一些点，这些点上有一些水果，经过此点就可收获此点上所有水果，水果不可再生，从某个给定点出发，最多走k步，问最多能收获多少水果。
思路
简单来说，本题只有两种情况，向一侧一直走k步，或者是先向一侧走i步，往回再走i步回到起点，再向另一侧走
k
−
2
i
k-2i
k−2i步。由此，我们可以处理出向左/向右走1~k步的答案，再处理折返的情况，这种情况下，我们假定终点为起点向左/向右偏移
i
(
i
∈
[
1
,
k
]
)
i(i in [1,k] )
i(i∈[1,k])步，并强制其先往另一侧走
(
k
−
i
)
/
2
(k-i)/2
(k−i)/2步，注意去掉起点处的水果数量，会重复计算一次。
代码
class Solution {
public:
unordered_map ma;
int maxTotalFruits(vector>& fruits, int startPos, int k) {
int n=fruits.size();
int dp[2][k+1];//dp[0][i]和dp[1][i]分别表示向左/向右走i步能获得的水果数量
for(int i=0;i 
