zoj 2042 - Divisibility

1299 단어 문제풀이 보고서DP(Dynamic Planning)
제목: 숫자의 순서를 바꾸지 않고 그들 사이에 마이너스나 플러스를 넣고 m을 정제할 수 있는지 물어본다.
분석:dp, 가방 유사물.용량은 0~m-1이다.
상태: f(i, j)는 전 i개수 조합 결과의 나머지가 j의 진짜 값이다.
이전: f(i, j)=max(f(i-1, j-a[i]), f(i-1), j+a[i]{결과 대응값은 0~m-1사이};
설명: (2011-9-19 11:24).
#include 
#include 
#include 
#include 

using namespace std;

bool F[ 10003 ][ 103 ];
int  N[ 10003 ];

int main()
{
    int t,n,k;
    while ( scanf("%d",&t) != EOF )
    while ( t -- ) {
        scanf("%d%d",&n,&k);
        for ( int i = 0 ; i < n ; ++ i )
            scanf("%d",&N[ i ]); 
        
        for ( int i = 0 ; i < n ; ++ i )
            N[ i ] = (k+N[ i ]%k)%k;
        
        memset( F, false, sizeof( F ) );
        F[ 0 ][ N[ 0 ] ] = true;
        
        for ( int i = 1 ; i < n ; ++ i ) 
        for ( int j = 0 ; j < k ; ++ j ) 
            if ( F[ i-1 ][ j ] ) {
                F[ i ][ (k+j-N[ i ])%k ] = true;
                F[ i ][ (k+j+N[ i ])%k ] = true;
            }
        
        if ( F[ n-1 ][ 0 ] )
            printf("Divisible
");
        else
            printf("Not divisible
");
        if ( t ) printf("
");
    }
    return 0;
}
AWS 미디어 서비스의 개요 및 사용 방법
Amazon WorkDocs 도입

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage