Подход сверху вниз для этой задачи программирования Dynami c

Question

Вот проблема -

Вам дан массив B размера n. Вы должны построить массив A так, чтобы 1 <= A [i] <= B [i] и сумма абсолютной разности последовательных пар A была максимизирована, то есть суммирование abs (A [i] -A [i -1]) максимизируется. Вы должны вернуть эту стоимость. </p>

Пример B = [1,2,3] A может быть [1,2,1], [1,1,3], [ 1,2,3] Во всех этих случаях стоимость равна 2, что является максимумом.

Ограничения n <= 10 ^ 5, 1 <= B [i] <= 100 </p>

Вот мой подход - Стоимость будет максимальной, когда A [i] = 1 или A [i] = B [i]

Итак, я создал dp [idx] [flag] [curr] размера [100002] [2 ] [102], где вычисляется стоимость до индекса idx. flag будет 0 или 1, представляя, должно ли A [i] быть 1 или B [i] соответственно. curr будет значением A [i] в ​​зависимости от флага

Вот мой код

     #include<bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long int ll;
#define mod 1000000007

 ll n;
ll dp[100002][2][101];
ll b[100005];
 ll solve(ll idx,ll flag,ll curr)
 {

     if(idx>=n)
         return 0;
     ll s1=0;
    if(dp[idx][flag][curr]!=-1)
        return dp[idx][flag][curr];
     if(idx==0)
     {
         int left=solve(idx+1,0,curr);
         int right=solve(idx+1,1,curr);
         return dp[idx][flag][curr]=max(left,right);
     }
     else
     {
         if(flag==0)
         {
             s1=abs(curr-1);
             return dp[idx][flag][curr]=s1+max(solve(idx+1,0,1),solve(idx+1,1,1));
         } 
         else
         {
             s1=abs(b[idx]-curr);
        return dp[idx][flag][curr]=s1+max(solve(idx+1,0,b[idx]),solve(idx+1,1,b[idx]));
         }
     }
 }


int main()
{
    boost
ll t;
cin>>t;
while(t--)
{ 
cin>>n;
memset(dp,-1,sizeof(dp));
ll res=0;
for(int i=0;i<n;i++)
    cin>>b[i];
ll s1=solve(0,0,1);//Starting from idx 0 flag 0 and value as 1
ll s2=solve(0,1,b[0]);//Starting from idx 0 flag 1 and value as B[0]
cout<<max(s1,s2)<<"\n";
}
}'

Есть ли способ уменьшить состояние dp или любого другого решения сверху вниз, потому что мой код не выполняется, если значения B [i] большие

Answer 1

Вы реализуете рекурсивный подход. Здесь простая итеративная реализация позволяет получить эффективность времени O (n) и эффективность использования пространства O (1) (не считая места, необходимого для входного массива).

Вы правильно указали, что в index i, у нас есть только два варианта: a[i]=1 (flag = 0) или a[i]=b[i] (flag = 1)

Основная идея c состоит в том, что при изучении того, какой выбор сделать в индексе i, нам нужно только знать, какие оптимальные суммы заканчиваются индексом i-1, для flag = 0 (sum0) или flag = 1 (sum1).

Нам не нужно явно вычислять массив a[.].

Примечание: я сохранил long long int как в вашем коде, но похоже, что int здесь вполне достаточно.

#include    <iostream>
#include    <cstdio>
#include    <vector>
#include    <cstdlib>
#include    <algorithm>

#define mod 1000000007          // needed ???

long long int sum_diff (const std::vector<long long> &b) {
    int n = b.size();
    long long int sum0 = 0;
    long long int sum1 = 0;
    for (int i = 1; i < n; ++i) {
        long long int temp = std::max (sum0, sum1 + b[i-1] - 1);            // flag = 0: a[i] = 1
        sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
        sum0 = temp;
    }
    return std::max (sum0, sum1);
 }


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    std::cin >> t;
    while(t--) { 
        int n;
        std::cin >> n;
        std::vector<long long int> b(n);
        for(int i = 0;i < n; i++) std::cin >> b[i];
        long long int s = sum_diff (b);
        std::cout << s << "\n";
    }
}

Поскольку вы настаиваете на нисходящем (рекурсивном) подходе, я реализовал оба подхода в следующем коде. Но я настаиваю на том, что итеративное решение в этом случае лучше.

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <vector>
#include    <algorithm>

int sum_diff (const std::vector<int> &b) {
    int n = b.size();
    int sum0 = 0;
    int sum1 = 0;
    for (int i = 1; i < n; ++i) {
        int temp = std::max (sum0, sum1 + b[i-1] - 1);                      // flag = 0: a[i] = 1
        sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
        sum0 = temp;
    }
    return std::max (sum0, sum1);
 }

 void sum_diff_recurs (const std::vector<int> &b, int i, int&sum0, int &sum1) {
    if (i == 0) {
        sum0 = sum1 = 0;
        return;
    }
    sum_diff_recurs (b, i-1, sum0, sum1);
    int temp = std::max (sum0, sum1 + b[i-1] - 1);                      // flag = 0: a[i] = 1
    sum1 = std::max (sum0 + b[i] - 1, sum1 + std::abs(b[i] - b[i-1]));  // flag = 1: a[i] = b[i]
    sum0 = temp;
 }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    std::cin >> t;
    while(t--) { 
        int n, sum0, sum1;
        std::cin >> n;
        std::vector<int> b(n);
        for(int i = 0; i < n; i++) std::cin >> b[i];
        int s = sum_diff (b);
        std::cout << s << "\n";
        sum_diff_recurs (b, n-1, sum0, sum1);
        std::cout << std::max(sum0, sum1) << "\n";
    }
}

Answer 2

На самом деле я нашел решение, используя только два состояния idx и flag

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll n,k;
ll dp[100002][2];
ll b[100005];

ll solve(ll idx,ll flag)
{
    if(idx>=n-1)
        return 0;
    if(dp[idx][flag]!=-1)
        return dp[idx][flag];
    ll val=(flag==1)?b[idx]:1;
    ll left=solve(idx+1,0)+val-1;
    ll right=solve(idx+1,1)+abs(val-b[idx+1]);
    return (dp[idx][flag]=max(left,right));
}

int main()
{ 
ll t;
cin>>t;
while(t--)
{ 
cin>>n;
memset(dp,-1,sizeof(dp));
ll res=0;
for(int i=0;i<n;i++)
    cin>>b[i];
ll s1=solve(0,0);
ll s2=solve(0,1);
cout<<max(s1,s2)<<"\n";
}
}