dynamic programming tablica 10^9

Question

https://codeforces.com/problemset/problem/996/A

Jest taki problem, no i rozwiazalem go greedy approachem:

#include <iostream>
 
using namespace std;
 
int main()
{
int n;
cin>>n;
int c=0;
while (n>0)
{
    if (n-100>=0)
    {
        n-=100;
        c++;
    }
    else if (n-20>=0)
    {
        n-=20;
        c++;
    }
    else if (n-10>=0)
    {
        n-=10;
        c++;
    }
    else if (n-5>=0)
    {
        n-=5;
        c++;
    }
    else if (n-1>=0)
    {
        n-=1;
        c++;
    }
}
cout<<c;
}

ale tez chcialem jak szef, i uzyc dynamic programming i mam tak:

#include <iostream>

using namespace std;

int main()
{
long long int n;
cin>>n;
long long int dp[n];
dp[0]=0;
int coins[5]={1,5,10,20,100};
for (long long i=1; i<n; i++)
    dp[i]=n+1;
for (long long i=1; i<=n; i++)
    for (int j:coins)
        if (i<j)
            continue;
        else
            dp[i]=min(dp[i], dp[i-j]+1);
cout<<dp[n];
}

no dalem wszedzie long longa zamiast inta ale i tak test: 

1000000000

crashuje, domyslam sie ze nie moge tworzyc tak duzych tablic, jak sobie z tym poradzic?

Comments

Alokujesz na stosie (VLA) tablicę o wielkości 10^9*8B, nie dziw

---

VLA nie jest równoważne z alokacja na stosie.

---

@lujasjeden,
W pętli masz odwołanie do elementu spoza zakresu tablicy dp, co jest UB, tym bardziej że zapisujesz tam wynik z funkcji min.

Answer 1

Poczytaj sobie o podziale pamięci na stos i stertę.
W twoim programie tablica jest tworzona na stosie. Na systemie Windows stos ma rozmiar 1MB. A ty próbujesz umieścić tam tablicę o rozmiarze 8GB (milion komórek po 8 bajtów).

Żeby użyć tak dużego bloku pamięci musisz ją zaalokować na stercie przy pomocy operatora new

auto tablica = new int[rozmiar_tablicy];

Aby uniknąć wycieku pamięci zwolnij zaalokowaną pamięć gdy nie będzie już potrzebna operatorem delete

delete [] tablica;

 

Comments

hmmm, no zaalokowalem to dynamicznie operatorem new, ale dalej dla testu 

1000000000

nie moge stworzyc tak duzej tablicy

terminate called after throwing an instance of 'std::bad_array_new_length'
  what():  std::bad_array_new_length

lub jak wpisze ten numer w talice zamiast n to dostaje:

error: size of array is too large|

kod: zamiast long longow jak sa inty to tez nie dziala,

#include <iostream>

using namespace std;

int main()
{
long long n;
cin>>n;
long long *dp;
dp=new long long [n];
dp[0]=0;
for (long long i=1; i<n; i++)
    dp[i]=n+1;
int coins[5]={1,5,10,20,100};
for (long long i=1; i<=n; i++)
    for (int j:coins)
        if (i<j)
            continue;
        else
            dp[i]=min(dp[i], dp[i-j]+1);
cout<<dp[n];
delete [] dp;
}

 

---

Stawiam, że jest tam x86. Na x86 VAS ma 2/3GB, a więc więcej nie zaalokujesz (chyba, że o czymś nie wiem?)

---

https://codeforces.com/problemset/problem/472/A

tak samo ten problem, mam taki kod:

#include <iostream>

using namespace std;

int main()
{
int n;
cin>>n;
int c[n];
bool k=false;
for (int i=1; i<=n; i++)
    c[i]=0;
for (int i=1; i<=n; i++)
    for (int j=1; j<=n/2; j++)
        if (i%j==0 && i!=j) c[i]++;
for (int i=1; i<=n; i++)
{
    for (int j=1; j<=n; j++)
    {
        if (c[i]>=2 && c[j]>=2 && i+j==n && k==false)
        {
            cout<<i<<" "<<j;
            k=true;
        }
    }
}
}

to dla testu : 

1000000

tez mi nie dziala, a jakies 12 czy 15 to wszystko smiga ladnie no i probowalem zaalokowac dynamicznie to tak samo