비트 마스크 - SPOJ LINEUP 틀린 대답

나는이 작업에 문제가있다. http://www.spoj.com/problems/LINEUP/ 꽤 쉽지만 내 솔루션이 실패합니다. 나는 잘못된 결과를 얻고있다. 누구든지 알아낼 수 있습니까? 어떤 도움을 주셔서 대단히 감사합니다. :-)비트 마스크 - SPOJ 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; 
}

출처

2013-10-26 Dario

코드가 올바른 결과를 내지 못하는 입력 (실제 및 예상 출력과 함께)을 입력해야합니다. – Dukeling

는 "모든 위치를 차지해야하지만, 그들은 (예 : \ 0의 점수가) 능숙하지 않은 위치에 플레이어를 넣지 마십시오."

확률값 [D]를 [I]은 = 현재 0 경우 확인해야합니다!

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

나머지는 좋은 것 같다.

출처

2013-10-26 20:17:00 DuX

나는 그것을 시도하지만 새로운 것은 없다. – Dario

새 코드 http://pastebin.com/gtFDhnp6 – Dario

때로는 prob [d] [i]가 모든 "i"에 대해 0이며 나머지 플레이어와 솔루션을 형성 할 수 없습니다. 이 경우 함수는 0을 반환하고 ("ret"는 0으로 초기화되기 때문에) "불가능"과 같은 값을 반환해야합니다. 나는 ret = -INF의 초기화가이 경우를 해결할 것이라고 생각한다. – DuX

문제는 할당 문제입니다. 헝가리 알고리즘을 사용하여 강점을 무효화하고 전체 약점을 최소화하십시오. 당신은 그것을 위해 구글 수 있습니다.

제로 강도는 매우 높은 긍정적 인 약점이 될 것입니다.

출처

2013-10-26 20:24:11

비트 마스크 - SPOJ LINEUP 틀린 대답

답변

관련 문제