Битовая маска — SPOJ LINEUP Неправильный ответ

У меня проблема с этой задачей. http://www.spoj.com/problems/LINEUP/ Это выглядит довольно просто, но мое решение не удалось. Я получаю неправильный результат.
Может кто-нибудь помочь разобраться? Большое спасибо за любую помощь. 🙂

#include <cstdio>
#include <string.h>
using namespace std;

int n;
int prob[21][21];

char vec_rijesio[1<<13];
int memo[1<<13];
int rijesi( int d, int s ) {
if ( d == 11 )
{
return 0;
}
if ( vec_rijesio[s] ) return memo[s];
vec_rijesio[s] = 1;
int &ret = memo[s];
ret = 0;

for ( int i=0; i<11; ++i )
if ( ( s & (1<<i) ) == 0 ) {
int tmp = prob[d][i] + rijesi(d + 1, s|(1<<i));
if ( tmp > ret ) ret = tmp;
}

return ret;
}

int main() {
scanf( "%d", &n );
for(int o=0;o<n;++o)
{
for ( int i=0; i<11; ++i )
for ( int j=0; j<11; ++j ) {
int x;
scanf( "%d", &x );
prob[i][j] = x;
}

int ret = rijesi( 0, 0 );
printf( "%d\n", ret);
memset (memo,0,sizeof(memo));
memset (vec_rijesio,0,sizeof(vec_rijesio));
}
return 0;
}

1

Решение

Проблема в задаче. Просто свести на нет сильные стороны и минимизировать общую слабость, используя венгерский алгоритм. Вы можете Google для этого.

Нулевая сила станет очень высокой положительной слабостью.

1

Другие решения

«Все позиции должны быть заняты, однако не ставьте игроков на позиции, с которыми они не владеют (то есть \ имеют оценку 0)».

Вы должны проверить, есть ли здесь prob [d] [i]! = 0:

int tmp = prob[d][i] + rijesi(d + 1, s|(1<<i));

В остальном вроде бы хорошо.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector