상태 압축 dp

5230 단어 dpcodeforces상태 압축

제목 링크:


codeforces 543C

제목 대의:


n개의 길이가 m인 문자열을 보여 줍니다. 모든 문자열은 다른 문자열과 구별되어야 합니다. 우리는 어떤 문자열을 수정하는 한 사람에게 고정된 비용이 있습니다. 요구에 맞는 문자열로 수정하는 데 최소한의 비용이 있는지 물어봅니다.

제목 분석:


4
  • 우리는 dp[i][state]를 정의하여 이전 i 문자열이state 상태에 도달했을 때의 최소 비용을 나타낸다

    • 4
  • 요구에 부합되지 않는 문자열에 대해 우리는 문자열이 소문자의 개수를 초과하지 않기 때문에 그 문자열을 수정하여 요구에 부합할 수 있다

    • 4
  • 현재 합법적인 상태 문자열로 변환하거나 이 문자열과 같은 문자를 가진 가장 큰 문자열을 제외한 다른 문자열을 직접 수정하여 이 문자열을 합법적으로 변환할 수 있다
  • i번째 문자열의 j번째 문자를 수정할 때 변환 방정식 충족:
    dp[i][state|(1<

    • 4
  • 문자열 세트의 j 문자를 수정하여 해당 문자열의 모든 합법적인 변환 방정식은 다음과 같습니다.
    dp[i][state|set]=min{dp[i−1][state]+costset[j]}
    우리는 단지 모든 상태를 일일이 열거하기만 하면 된다

    • AC 코드:

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1<<21];
char s[26][26];
int c[26][26];
int v[26][26];
int state[26][26];
int n,m;

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &m ) )
    {
        for ( int i = 0 ; i < n ; i++ )
            scanf ( "%s" , s[i] );
        for ( int i = 0 ; i < n ; i++ )
            for ( int j = 0 ; j < m ; j++ )
               scanf ( "%d" , &c[i][j] );
        int total = (1<<n)-1;
        for ( int i = 0 ; i < n ; i++ )
            for ( int k = 0 ; k < m ; k++ )
            {
                int maxn = 0;
                for ( int j = 0 ; j < n ; j++ )
                {
                    if ( s[i][k] != s[j][k] ) continue;
                    v[i][k] += c[j][k];
                    maxn = max ( c[j][k] , maxn );
                    state[i][k] |= 1<<j;
                }
                v[i][k] -= maxn;
            }
        memset ( dp , 0x3f , sizeof ( dp ) );
        dp[0] = 0;
        for ( int i = 0 ; i < total ; i++ )
            for ( int j = 0 ; ; j++ )
                if ( !((i>>j)&1))
                {
                    int a = 1<<j;
                    for ( int k = 0 ; k < m ; k++ )
                    {
                        int b = state[j][k];
                        dp[i|a] = min ( dp[i|a] , dp[i] + c[j][k] );
                        dp[i|b] = min ( dp[i|b] , dp[i] + v[j][k] );
                    }
                    break; 
                }
        printf ( "%d
    "     , dp[total] );
    }
}
    [openjudge] 와일드카드 문자열 일치 (dp)
    AWS CDK에서 Docker 및 VScode를 사용하여 로컬 환경 만들기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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