Pitanje ili opis problema
Zadatak sa SPOJa
Link ka zadatku ili odgovarajućoj stranici
Postovani,
Naleteo sam skoro na ovaj problem i imam TLE zbog velike kompleksnosti. Koliko shatam imam sort sto je O(nlogn) valjda + knapsack problem (samo ne igram loto nego stavljam resenja u vektor) sto je O(n(n+1)/2) (svaki sa svakim u najgorem slucaju)
Ovo je kod:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class voznja
{
public:
int cena=0, plus=0, visina=0;
voznja();
voznja(int, int, int);
bool operator <(voznja);
};
class triplet
{
public:
int x1, x2, x3;
triplet();
triplet(int, int, int);
};
triplet::triplet(int j, int k, int l)
{
x1=j;
x2=k;
x3=l;
}
voznja::voznja(int x, int y, int z)
{
cena=y;
visina=x;
plus=z;
}
bool voznja::operator<(voznja neka)
{
if(visina<neka.visina)return true;
else if(visina>neka.visina)return false;
else
{
if(cena<neka.cena)return true;
else return false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
vector<voznja> c;
vector<triplet> stanja;
int n, m, h, w1, w2, w3, cnt=0, maxi=-1;
cin>>n>>m>>h;
for(int i=0; i<n; i++)
{
cin>>w1>>w2>>w3;
if(w2==0)cnt++, h+=w3;
else if(w2<m)
c.push_back(voznja(w1, w2, w3));
}
sort(c.begin(), c.end());
stanja.push_back(triplet(h, m, cnt));
for(voznja v : c)
{
for(int i=stanja.size()-1; i>=0; i--)
{
if(v.visina<=stanja[i].x1 && v.cena<=stanja[i].x2)
{
stanja.push_back(triplet(stanja[i].x1+v.plus, 0-v.cena+stanja[i].x2, stanja[i].x3+1)); if(maxi<stanja[i].x3+1)maxi=stanja[i].x3+1;
}
}
}
cout<<maxi;
return 0;
}
Ako postoji neko dinamicnije resenje bio bih zahvalan na sugestiji
PS: pod loto mislim da se knapsack ne radi preko niza sa nulama pa tu satvim 1 ako postoji vrednost, tako sam ucio knapsack pa cisto da napomenem