→ bollseven: 加油 01/19 12:27
推 Meaverzt: 大師 01/19 12:30
推 Furina: 我好崇拜你 01/19 14:01
我又進1000名了
家人們
我有一天會拿到Guardian 的
雖然可能要拿一輩子
一輩子...
Q1
每一個i-nums[i] 到 n的元素和
思路
照做
```cpp
class Solution {
public:
int subarraySum(vector<int>& nums)
{
int n = nums.size();
int res = 0;
for(int i = 0 ; i < n ; i ++)
{
int start = max(0 , i - nums[i]);
for(int j = start ; j <= i ; j ++)
{
res += nums[j];
}
}
return res;
}
};
```
Q2
最多k個元素的集合 不用連續
求他們的最大最小值的總合
思路
先sort之後就可以確定每次的最大最小值
然後就可以用C n取k 算出有多少組合
這些組合就是包含當前極值的所有集合
然後全部加起來
```cpp
class Solution {
public:
int minMaxSums(vector<int>& nums, int k)
{
long long res = 0;
int n = nums.size();
vector<vector<long long>> comb(n + 1, vector<long long>(k + 1, 0));
for (int i = 0; i <= n; i++) {
comb[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j > i) break;
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
comb[i][j] %= 1000000007;
}
}
sort(nums.begin() , nums.end());
for(int i = 0 ; i < n ; i ++)
{
for(int take = 0 ; take < min( k , n - i ) ; take ++)
{
long long now = nums[i] * comb[n-i-1][take] ;
now %= 1000000007;
res += now ;
res %= 1000000007;
}
}
for(int i = n-1 ; i >= 0 ; i --)
{
for(int take = 0 ; take < min( k , i+1 ) ; take ++)
{
long long now = nums[i] * comb[i][take] ;
now %= 1000000007;
res += now ;
res %= 1000000007;
}
}
return res%1000000007;
}
};
```
Q3
一串房子 三種顏色跟他們的cost
相鄰不可以同色
對稱 (i,n-1-i)不可以同色
思路
dp
然後看每種顏色的組合
大概會是
123
1x
2 x
3 x
因為相鄰不能同色
所以不能到同直或橫排
對稱不能是同色
所以不能到11 22 33也就是x的地方
然後dp就好了
class Solution {
public:
long long minCost(int n, vector<vector<int>>& cost)
{
// n L(a) R(
b)
vector<vector<vector<long long>>> paper(n/2,vector<vector<long long>>(3,
vector<long long>(3)));
for(int a = 0 ; a < 3 ; a ++)
{
for(int b = 0 ; b < 3 ; b ++)
{
if(a == b)continue;
paper[0][a][b] = cost[0][a] + cost[n-1][b];
}
}
for(int i = 1 ; i < n/2 ; i ++)
{
long long pre2 = paper[i-1][1][0];
long long pre3 = paper[i-1][2][0];
long long pre4 = paper[i-1][0][1];
long long pre6 = paper[i-1][2][1];
long long pre7 = paper[i-1][0][2];
long long pre8 = paper[i-1][1][2];
for(int a = 0 ; a < 3 ; a ++)
{
for(int b = 0 ; b < 3 ; b ++)
{
if(a == b)continue;
long long nowcost = cost[i][a] + cost[n-1-i][b];
long long precost = 0 ;
if (a == 0) {
if (b == 1) precost = min(pre2, min(pre3, pre8));
if (b == 2) precost = min(pre2, min(pre3, pre6));
}
if (a == 1) {
if (b == 0) precost = min(pre4, min(pre6, pre7));
if (b == 2) precost = min(pre4, min(pre3, pre6));
}
if (a == 2) {
if (b == 0) precost = min(pre4, min(pre8, pre7));
if (b == 1) precost = min(pre2, min(pre7, pre8));
}
paper[i][a][b] = precost + nowcost;
}
}
}
// for(int i = 0 ; i < n/2 ; i ++)
// {
// for(int a = 0 ; a < 3 ; a ++)
// {
// for(int b = 0 ; b < 3 ; b ++)
// {
// cout << paper[i][a][b] << " ";
// }
// cout << endl;
// }
// cout << "--------" <<endl;
// }
long long res = LLONG_MAX;
for(int a = 0 ; a < 3 ; a ++)
{
for(int b = 0 ; b < 3 ; b ++)
{
if(a == b)continue;
res = min(res , paper[n/2 - 1][a][b]);
}
}
return res;
}
};
// 123
//
// 1 X23
// 2 4X6
// 3 78X
// 2 : 4 6 7
// 3 : 4 7 8
// 4 : 2 3 8
// 6 : 2 7 8
// 7 : 2 3 6
// 8 : 3 4 6
Q4
我根本沒看
誰他媽寫的玩
--
我是小黃瓜
https://i.imgur.com/1YMQtyf.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.154.84 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737260827.A.550.html