#include #include #define MAX(a,b) ( ( (a) > (b) ) ? (a) : (b) ) #define MAXN 1000 char A[MAXN], H[MAXN]; // amulet a heslo int zdroj[MAXN]; // zdroj[i] == ze které pozice v původním amuletu pochází // korálek recyklovaný v hesle na pozici $i$ int LA, LH; // ... a jejich délky char C[MAXN+1][MAXN+1]; // pomocná tabulka pro hledání NSP int cr, cg, cb; int cena(char koralek) { switch (koralek) { case 'R': return cr; case 'G': return cg; case 'B': return cb; default: abort(); } } // http://en.wikipedia.org/wiki/Longest_common_subsequence#Computing_the_length_of_the_LCS int LCSLength() { for (int i = 0; i <= LA; i++) C[i][0] = 0; for (int j = 0; j <= LH; j++) C[0][j] = 0; for (int i = 1; i <= LA; i++) for (int j = 1; j <= LH; j++) { if (A[i-1] == H[j-1]) // posloupnosti číslujeme od nuly! C[i][j] = C[i-1][j-1] + cena(A[i-1]); else C[i][j] = MAX(C[i][j-1], C[i-1][j]); } return C[LA][LH]; } // http://en.wikipedia.org/wiki/Longest_common_subsequence#Reading_out_an_LCS // Ale nevrací obsah NSP, místo toho naplní pole zdroj[]. // A rekurze nahrazena smyčkou. void backtrack() { for (int t = 0; t < LH; t++) zdroj[t] = -1; int i = LA, j = LH; while (i > 0 && j > 0) { if (A[i-1] == H[j-1]) { zdroj[j-1] = i-1; i--; j--; } else { if (C[i][j-1] > C[i-1][j]) j--; else i--; } } } void vypis() { // Pro nerecyklované (nové) korálky do pole za[] uložíme zdroj // nejbližšího recyklovaného korálku nalevo, tedy ten korálek // z původního amuletu, za který chceme vkládat. int za[MAXN]; int posledni_zdroj = -1; for (int i = 0; i < LH; i++) { if (zdroj[i] != -1) { // recyklovaný korálek za[i] = -1; // nevkládáme posledni_zdroj = zdroj[i]; // ale zapamatujeme si zdroj // pro další použití } else { // nový korálek za[i] = posledni_zdroj; } } // A vypíšeme informace o vložených korálcích odzadu for (int i = LH - 1; i >= 0; i--) { if (za[i] != -1) printf("Za koralek cislo %d vloz koralek barvy %c\n", za[i]+1, H[i]); } } // Formát vstupu: // cR cG cB LA LH // // // // Ukázkový vstup: // 1 1 1 9 6 // RRRGGGBBB // RGBRGB // // Ukázkový výstup: (číslováno od jedničky) // Za koralek cislo 1 vloz koralek barvy B // Za koralek cislo 1 vloz koralek barvy G void main(int argc, char *argv[]) { scanf("%d %d %d %d %d %s %s", &cr, &cg, &cb, &LA, &LH, A, H); LCSLength(); backtrack(); vypis(); }