【每日刷题】Day146

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. mari和shiny

2. 组队竞赛__牛客网

3. 删除相邻数字的最大分数_牛客题霸_牛客网

1. mari和shiny

//思路：动态规划

//本题多状态dp

#include<iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin>>n;
    getchar();
    string str;
    getline(cin,str);
    vector<long long> s(n);//记录字符 's' 的个数
    vector<long long> h(n);//记录字符 'sh' 的个数
    vector<long long> sh(n);//记录字符 'shy' 的个数
    s[0] = str[0]=='s'?1:0;
    for(int i = 1;i<n;i++)
    {
        s[i] = str[i]=='s'?s[i-1]+1:s[i-1];
        h[i] = str[i]=='h'?s[i-1]+h[i-1]:h[i-1];
        sh[i] = str[i]=='y'?h[i-1]+sh[i-1]:sh[i-1];
    }
    cout<<sh[n-1];
    return 0;
}

2. 组队竞赛__牛客网

//思路：贪心+排序

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

    int n;

    long long ans = 0;

    cin>>n;

    int size = 3*n;

    vector<int> arr(size);

    for(int i = 0;i<size;i++) cin>>arr[i];

    sort(arr.begin(),arr.end());//排序

    int left = 0,right = size-2;

    while(left<right)

    {

        ans+=arr[right];

        left++;//left每次选择数组中最小的数

        right-=2;//right每次选择数组中第二大的数

    }

    cout<<ans;

    return 0;

}

3. 删除相邻数字的最大分数_牛客题霸_牛客网

//思路：动态规划 

//本题思路实际上与 "打家劫舍" 完全一样，但是需要我们对原数据进行统合：

//如果没有做过 "打家劫舍" 这道题可以去看一下这道题的题解  Day 115

int boredom(vector<int>& a)

    {

        int ans = 0,boundary = 0;//boundary用于减少空间的浪费

        vector<int> hash(10001);

        for(auto i:a)

        {

            hash[i]+=i;

            boundary = boundary>i?boundary:i;//记录 a 数组中的最大元素，hash以及 dp1 和 dp2 的边界就是 boundary

        }

        vector<int> dp1(boundary+1);

        vector<int> dp2 = dp1;

        dp1[0] = hash[0];

        for(int i = 1;i<=boundary;i++)//打家劫舍

        {

            dp1[i] = dp2[i-1]+hash[i];

            dp2[i] = max(dp2[i-1],dp1[i-1]);

        }

        for(auto i:dp1) ans = ans>i?ans:i;

        return ans;

    }

};