Текущ брой на Списание ИнфоМан
 


НОИ 2005 - 3 кръг, Задача A2. ОПЕРАЦИЯ

Уловието на задачата може да прочетете тук.

Решение

При всяко разделяне със скоби последната операция, която ще бъде приложена, няма нужда да се огражда в скоби. Освен това целият израз от ляво и целият отдясно ще са обградени в скоби, за да бъдат изцяло пресметнати преди последната операция.

Нека при всевъзможните поставяния на скоби на единия подизраз се получават резултатите r1, r2, …, rq. Нека от другия подизраз се получават резултатите s1, s2, …, sp. Тогава след извършването на последната операция се получават резултати ri * sj (за всички i от 1 до q и всички j от 1 до p).

Нека са известни резултатите при всевъзможните разделяния със скоби на всички подредици от числа ai. Всички резултати на целия израз се получават като се разгледат случаите всяка една от операциите да бъде последна.

Резултатите на по-малките изрази се получават по същия начин.

Решението на задачата се основава на горните разсъждения. Първо се намират всевъзможните резултати на изразите от две числа, след това – на тези от три числа и т.н. Накрая се получават резултатите, които могат да се получат от целия израз. Алгоритъмът има сложност O(k2*n3): със сложност O(n3) се разглеждат подпоследователности с всякаква дължина, които започват от всеки възможен индекс и за всяка от тях се разглеждат всички възможности за последна операция; обединението на получаваните решения се извършва със сложност O(k2).

Примерна реализация

/*
TASK:oper
LANG:C++
*/
# include <stdio.h>
# define MAXK 128
# define MAXN 32

//din[x][y] means the numbers from the x-th to the y-th.
//in din[x][y] are stored all the possible results
bool din[MAXN][MAXN][MAXK];

//stores the definition of the function
char t[MAXK][MAXK];
int n,k;

void readf() {

    int buf;

    scanf("%d",&k);
    for ( int i=1 ; i<=k ; i++ ) {
        for ( int j=1 ; j<=k ; j++ ) {
            scanf("%d",&t[i][j]);
        }
    }

    scanf("%d",&n);
    for (int i=1 ; i<=n ; i++ ) {
        scanf("%d",&buf);
        din[i][i][buf] = 1;    
    }    
}

void solve() {
    //For each length
    for ( int l=1 ; l<n ; l++ ) {
        //and each beginning,
        for ( int i=1 ; i+l<=n ; i++ ) {
            //for each separator,
            for ( int j=i ; j<i+l ; j++ ) {
                //each number is checked
                for ( int q=1 ; q<=k ; q++ ) {
                    //whether is a solution and if so
                    if ( din[i][j][q]==1 ) {
                        //for each number
                        for ( int p=1 ; p<=k ; p++ ) {
                            //that is solution in the remaining sequence
                            if ( din[j+1][i+l][p] ) {
                                //the result is added
                                din[i][i+l][t[q][p]] = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    int br=0;
    for ( int i=1 ; i<=k ; i++ ) {
    if ( din[1][n][i] ) br++;
    }
    printf("%d\n",br);
}

int main() {
    readf();    //input
    solve();    //solution

    return 0;
}



Автор: Никола Борисов


обратно към текущ брой