Java教程

用动态规划算法求数列中三个数的最大值,且该三个数的下标间距需大于等于K

本文主要是介绍用动态规划算法求数列中三个数的最大值,且该三个数的下标间距需大于等于K,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 题目描述
程序设计竞赛的参赛队伍通常由3人组成。如何从学生中选出三人组成最强的队伍而又不失公平(即不让选出的学生均集中在个别班级里)呢。虽然每个班级的学生人数有出入,但上限是固定的,并且同一个教学班的学生其学号是连续编号的,由此设计出一个即公平(每个班最多选1人)又便利(不用分班)的最强队伍选择方法。

输入格式:
输入两行数据,第一行给出两个正整数N和K,表示学生总人数和班级人数上限,满足2K<N≤10^5(至少有三个班)。
接下来一行给出N个正整数,用空格分开,依次表示从学号0到学号N-1的学生成绩。
末尾的成绩后面没有空格。所有成绩值都在区间[1,10^5]以内。

输出格式:
输出两行数据。第一行给出选出的最强队伍的总成绩;
第二行给出组队的三名学生的学号a  b  c,满足 b−a≥K∧c−b≥K。
数值间用空格分开,末尾不留空格。 
如果最强队伍有多组,输出学号序列字典序最小的队伍。

输入样例1:
10 3
6 2 7 8 9 2 8 5 7 1
输出样例1:
22
0 3 6
注:学号0+学号4+学号8也是最强队伍,但字典序较大。

2.方法一:
暴力求解 ,通过对三个数的下标的范围进行限制,在该范围内遍历求解。因为是从小到大遍历的,所以即使后面存在跟前面最高分数一样的解,字典序也是比之前大的,不需要考虑。但是该算法时间复杂度较大,会超时,

#include <iostream>
#include <stdlib.h>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct strong
{
    int score;
    string compare;
    int num[3];
};


int main()
{
    int N,K;
    cin >> N >> K;
    int * ps = new int[N];
    for(int i=0; i<N; i++)
    {
        cin >> ps[i];
    }
    strong maxes;
    int maxscore = 0;
    int flag = 0;
    for(int i=0; i<N-2*K; i++)
    {
        for(int j=i+K;j<N-K;j++)
        {
            for(int s=j+K;s<N;s++)
            {
                int scores = ps[i] + ps[j] + ps[s];
                if(scores > maxscore)
                {
                    maxscore = scores;
                    string bian = to_string(i)+to_string(j)+to_string(s);
                    
                        maxes.num[0] = i;
                        maxes.num[1] = j;
                        maxes.num[2] = s;
                        maxes.compare = bian;
                        maxes.score = maxscore;
                   
                }
               
            }
        }
    }
        cout << maxscore << endl;
        for(int i=0; i<3; i++)
        {
            if(i==0)
            {
                cout << maxes.num[i];
            }
            else
            {
                cout << " " << maxes.num[i];
            }
        }
   
    return 0;
    
}

3.方法二:动态规划
思路:
left数组:left[i]表示从0~i中最大元素所在的下标。
right数组: right[i]表示从末尾到当前位置i中最大元素所在的下标。
b的下标一定位于[K,N-K]范围内,对这个范围里的b进行遍历,求出最高分数并记录对应的a,b,c;
在这里插入图片描述

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

int main()
{
    int N,K;
    cin >> N >> K;
    vector<int> nums;
    int s;
    for(int i=0; i<N; i++)
    {
        cin >> s;
        nums.push_back(s);
    }
    vector<int> left(N,0), right(N,N-1);
    for(int i=1; i<N; i++)
    {
        if(nums[i]>nums[left[i-1]])
            left[i] = i;
        else
            left[i] = left[i-1];
        
    }
    for(int i=N-2; i>=0; i--)
    {
        if(nums[i] >= nums[right[i+1]])
            right[i] = i;
        else
            right[i] = right[i+1];
    }
    int max = 0;
    vector<int> index(3);
    for(int i=K; i<N-K; i++)
    {
        if(max<nums[i]+nums[left[i-K]]+nums[right[i+K]])
        {
            max = nums[i]+nums[left[i-K]]+nums[right[i+K]];
            index = {left[i-K],i,right[i+K]};
        }
    }
    cout << max<< endl;
    cout << index[0] << " " << index[1] << " " << index[2] << endl;
}

会了的小朋友就可以去看看这道题哦
https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/

这还不点赞收藏,快跟我一起升级打怪变成编程大佬叭。

这篇关于用动态规划算法求数列中三个数的最大值,且该三个数的下标间距需大于等于K的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!