Hackerrank Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence.
You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)].
For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence :

We call it increasing if for every i (1 <= i M ) , bi < bi+1.

Weight(B) = v1 + v2 + ... + vM.

Task: Given a sequence, output the maximum weight formed by an increasing subsequence.
Input: The first line of input contains a single integer T. T test-cases follow. The first line of each test-case contains an integer N. The next line contains a1, a2 ,... , aN separated by a single space. The next line contains w1, w2, ..., wN separated by a single space.
Output: For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence.
Constraints: 1 <= T <= 5 1 <= N <= 150000 1 <= ai <= 109, where i ∈ [1..N] 1 <= wi <= 109, where i ∈ [1..N]
Sample Input:

2  
4  
1 2 3 4  
10 20 30 40  
8  
1 2 3 4 1 2 3 4  
10 20 30 40 15 15 15 50

Sample Output:

100  
110

Explanation: In the first sequence, the maximum size increasing subsequence is 4, and there's only one of them. We choose B = [(1, 10), (2, 20), (3, 30), (4, 40)] , and we have Weight(B) = 100 .
In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:

1 2 3 4  
10 20 30 40

1 2 3 4  
10 20 30 50

1 2 3 4  
10 20 15 50

1 2 3 4  
10 15 15 50

1 2 3 4  
15 15 15 50

Of those, the one with the greatest weight is B = [(1, 10), (2, 20), (3, 30), (4, 50)] , with Weight(B) = 110 .
Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.
제목: 두 개의 서열과 가장 큰 요구를 가진 두 번째 서열을 정하고 첫 번째 서열을 만족시키는 것이 점차 증가한다.
해법: 이 문제의 배경은 경전의 최대 상승자 서열과다.그러나 그것이 O(n^2) 알고리즘이라는 것을 감안하면이것을 토대로 최적화를 해야 한다.
해법1: 단조로운 set 유지
우리가 큰 숫자를 얻으면 가능한 한 큰 값을 얻을 수 있다는 것을 확신할 수 있다.이것도 단조로운 의미다.
만약 하나의 수가 크지만 권한과 값이 작다면, 우리는 이 수를 고려하지 않을 수 있다. 왜냐하면 그것보다 작은 수가 더 큰 서열을 구성할 수 있기 때문이다.
우선 이산화, 모든 숫자를 정렬하고 1부터 증가하는 수열로 이산화하기(map)
val[i]로 이 숫자가 구성할 수 있는 최대 값을 나타낸다.
그리고 삽입할 때마다 뒤로 유지보수를 하고 단조성에 맞지 않는 요소를 제거합니다.
찾을 때 2분 동안.
그런데 이게 사실 느려요. 1초 넘게 걸려요.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pii pair
#define vi vector
#define ll long long
#define eps 1e-3
using namespace std;
const int maxn = 2e5 + 10;
map ind;
ll a[maxn];
ll w[maxn];
set temp;
ll val[maxn];
int main()
{
    //freopen("/Users/vector/Desktop/in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        temp.clear();
        memset(val, 0, sizeof(val));
        ind.clear();
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            temp.insert(a[i]);
        }
        for(int i = 0; i < n; i++)
            cin >> w[i];
        int id = 1;
        for(auto idx: temp)
            ind[idx] = id++;
        temp.clear();
        for(int i = 0; i < n; i++)
        {
            int q = ind[a[i]];
            /*for(auto idx = temp.rbegin(); idx != temp.rend(); idx++)
            {
                int elm = *idx;
                //cout << elm << endl;
                if(q > elm)
                {
                    temp.insert(q);
                    val[q] = max(val[q], val[elm] + w[i]);
                    f = 1;
                    break;
                }
            }*/
            set :: iterator io = temp.lower_bound(q);
            if(io == temp.begin())
            {
                temp.insert(q);
                val[q] = max(val[q], w[i]);
            }
            else
            {
                io--;
                int elm = *io;
                temp.insert(q);
                val[q] = max(val[q], val[elm] + w[i]);
            }
            set :: iterator t = temp.find(q);
            vector del;
            for(; t != temp.end(); t++)
            {
                if(val[*t] < val[q])
                    del.push_back(*t);
            }
            for(auto idx: del)
                temp.erase(idx);
            //cout << endl;
        }
//        for(auto t: temp)
//            cout << t << ' ';
        int ed = *temp.rbegin();
        cout << val[ed] << endl;


    }
    return 0;
}

해법2: 수상수 그룹 (bit)
수상수 그룹으로 구간의 최대 값을 유지합니다. (기억하십시오: 수상수 그룹도 구간의 최대 값을 유지할 수 있습니다.)
읽기, 지우기, 각 숫자는 작은 것부터 큰 것까지 0, 1, 2로 대응한다.
그리고 매번 한 수를 처리하고lowerbound 찾기는 그것의 첫 번째 수보다 크다. 나무 모양의 수조의 하표는 1부터 시작하기 때문에, 여기서 바로 앞의 수를 찾는다
조회 1 - 현재 아래 표시된 최대값 + w[i]
다시 업데이트하면 됩니다.아니면 아래 첨자로 인해 업데이트할 사람이 다음 사람입니까?교묘하네.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pii pair
#define vi vector
#define ll long long
#define eps 1e-3
using namespace std;
const int maxn = 2e2 + 10;
map ind;
int w[maxn];
int val[maxn];
ll bit[maxn];
int n;
void update(int x, ll v)
{
    while(x < maxn)
    {
        bit[x] = max(bit[x], v);
        x += x & -x;
    }
}
ll query(int x)
{
    ll res = 0;
    while(x)
    {
        res = max(res, bit[x]);
        x -= x & -x;
    }
    return res;
}
int main()
{
    //freopen("/Users/vector/Desktop/in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        vi a(n), b(n);
        for(int i = 0; i < n; i++)
            cin >> a[i];
        b = a;
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()), b.end());//     
//        for(auto idx: b)
//            cout << idx  << ' ' ;
        for(int i = 0; i < n; i++)
            cin >> w[i];
        ll ans = 0;
        memset(bit, 0, sizeof(bit));
        //bit     1            
        for(int i = 0; i < n; i++)
        {
            int pos = (int)(lower_bound(b.begin(), b.end(), a[i]) - b.begin());
            ll temp = query(pos) + w[i];
            ans = max(temp, ans);
            update(pos + 1, temp);//            bit     1   
        }
        cout << ans << endl;
        
    }
    return 0;
}
/*
2
4
1 2 3 4
10 20 30 40
8
1 2 3 4 1 2 3 4
10 20 30 40 15 15 15 50
*/

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

백준 10844번 쉬운 계단 수 - node.js

문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Hackerrank Subsequence Weighting

좋은 웹페이지 즐겨찾기