Dobra, udało mi się zrozumieć ;)
Najbardziej psuje sprawę ten zakres tolerancji, lepiej byłoby gdyby najpierw decydowała o wyniku ilość słów a potem dopiero waga ale to by było za proste :D
Jakiej złożoności oczekujesz?
abym się upewnił, że dobrze zrozumiałem:
ciąg: ABC waga: 15
ciąg: DECA waga: 13
ciąg: TSU waga: 10
ciąg: DAW waga: 9
ciąg: ABCEA waga: 7
Drugi zbiór ciągów znaków posiada jedynie znaki np:
ciąg: ABC
ciąg: DECA
ciąg: ABCEA
|
w tym przypadku niektóre ciągi z pierwszego zbioru są zbędne, tak?
czyli można to równie dobrze przedstawić jako
ciąg: ABC waga: 15
ciąg: DECA waga: 13
ciąg: ABCEA waga: 7
//
ok, jeśli dobrze zrozumiałem treść zadania:
złożoność: O(n log n)
1. tworzysz sobie struktury tak jak powyżej (wyrazenie,waga)
2. sortujesz je względem wag (O(n log n))
3. tworzysz sobie tablicę z wynikami
4. do elementu tab[1] zapisujesz sumę wag jakie możesz uzyskać biorąc jedynie wyrażenie o największej wadze (wyrazenie_o_najwiekszej_wadze.waga * ilosc_wyrazen_jakie_mamy_wziac)
5. do elementu tab[2] zapisujesz sumę wag jakie możesz uzyskać biorąc n-1 wyrażeń o największej wadze (gdzie n to ilość dostępnych różnych wyrażeń) oraz 1 wyrażenie kolejno niżej z największą wagą
6. do elementu tab[3] zapisujesz sumę wag jakie możesz uzyskać biorąc n-2 wyrażeń o największej wadze, 1 wyrażenie kolejno niżej z największą wagą, 1 wyrażenie kolejno niżej z największą wagą
7. itd...
tab:
Ilosc wyrazen: (i) 1 2 3 4 5 6 7 8 9 ...
Maksymalna możliwa waga do uzyskania: (tab[i]) ... ... ... ...
tab[i] to maksymalna możliwa waga do uzyskania dla i różnych wyrażeń
8. teraz wybierasz elementy z tablicy tab[i] które są w zakresie max(tab[i])-ZAKRES_TOLERANCJI do max(tab[i]) (gdzie max to największa wartość jaką zawiera tablica)
9. z wybranych elementów wybierasz ten, który ma najwięcej różnych wyrażeń (czyli ten o największym i)
(rozwiązanie polega na tym, że zawsze przecież najbardziej opłaca się brać te wyrażenia o największej wadze a ilościowo dopełniać po jednym innym słowie z mniejszą wagą, nigdy nie opłaca się brać 3 elementów o największej wadze i 2 elementów o wadze niższej skoro można wziąć 4 elementy o największej wadze i 1 element o wadze niższej nie tracąc przy tym ilości różnych wyrażeń)
//edit
(złożoność taka jaką podałem wyżej, dla n log n program działa w sensowym czasie nawet dla 1000000 ciągów):
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
const int TOLERANCJA = 40;
class Cwyrazenie
{
public:
std::string str;
int waga;
int suma_do_mnie;
Cwyrazenie() { }
Cwyrazenie( const std::string new_str, const int new_waga )
: str( new_str )
, waga( new_waga )
{
}
~Cwyrazenie() { }
};
class Cwyrazenie_max
{
public:
int ilosc_roznych_wyrazen;
int maksymalna_waga;
Cwyrazenie_max() { }
Cwyrazenie_max( const int new_ilosc_roznych_wyrazen, const int new_maksymalna_waga )
: ilosc_roznych_wyrazen( new_ilosc_roznych_wyrazen )
, maksymalna_waga( new_maksymalna_waga )
{
}
~Cwyrazenie_max() { }
};
bool wyrazenie_mniejsze( const Cwyrazenie wyr1, const Cwyrazenie wyr2 )
{
return wyr1.waga < wyr2.waga;
}
int main()
{
std::vector < Cwyrazenie > wyrazenie;
int n, ilosc_wyrazen;
scanf( "%d", & n );
std::string tmp_str;
int tmp_waga;
for( int i = 0; i < n; ++i ) {
std::cin >> tmp_str >> tmp_waga;
wyrazenie.push_back( Cwyrazenie( tmp_str, tmp_waga ) );
}
sort( wyrazenie.begin(), wyrazenie.end(), wyrazenie_mniejsze );
if( wyrazenie.size() >= 2 )
for( int i = int( wyrazenie.size() - 2 ); i >= 0; --i ) {
if( i == int( wyrazenie.size() - 2 ) ) wyrazenie[ i ].suma_do_mnie = wyrazenie[ i ].waga;
else wyrazenie[ i ].suma_do_mnie = wyrazenie[ i ].waga + wyrazenie[ i + 1 ].suma_do_mnie;
}
scanf( "%d", & ilosc_wyrazen );
int * suma_wag = new int[ std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1 ];
for( int i = 0; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ); ++i ) {
suma_wag[ i + 1 ] = wyrazenie[ wyrazenie.size() - 1 ].waga *( ilosc_wyrazen - i );
if( i != 0 ) suma_wag[ i + 1 ] += wyrazenie[ wyrazenie.size() - 1 - i ].suma_do_mnie;
}
int maksymalna_mozliwa_waga =- 1;
for( int i = 1; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1; ++i ) {
if( suma_wag[ i ] > maksymalna_mozliwa_waga ) maksymalna_mozliwa_waga = suma_wag[ i ];
}
std::vector < Cwyrazenie_max > wyrazenie_max;
for( int i = 1; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1; ++i ) {
if( suma_wag[ i ] >= maksymalna_mozliwa_waga - TOLERANCJA ) wyrazenie_max.push_back( Cwyrazenie_max( i, suma_wag[ i ] ) );
}
int best_indeks = 0;
int max_ilosc_roznych_wyrazen =- 1;
for( size_t i = 0; i < wyrazenie_max.size(); ++i ) {
if( wyrazenie_max[ i ].ilosc_roznych_wyrazen > max_ilosc_roznych_wyrazen ) {
max_ilosc_roznych_wyrazen = wyrazenie_max[ i ].ilosc_roznych_wyrazen;
best_indeks = i;
}
}
printf( "%d\n", wyrazenie_max[ best_indeks ].maksymalna_waga );
}
dla pierwszego testu, który podałeś (przy zachowaniu tolerancji 40) najlepszym możliwym wynikiem jest 140