codeforces 225C C. Barcode(dp)

5515 단어 dpcodeforces

제목 링크:


codeforces 225C

제목 대의:


두 가지 색을 포함하는 행렬을 보여 줍니다. 최소한 몇 개의 점을 수정해야 각 열의 색깔이 일치하고, 색깔이 일치하는 연속적인 열의 길이는 x와 y 사이입니다.

제목 분석:


4
  • 우선 우리는 모든 열을 전체 흑열로 조정하고 전체 백열로 조정하는 비용을 통계한 다음에 상태 dp[i][j][k]를 현재 처리된 i열로 정의하고 현재 색깔은 k이며 연속 열의 길이는 j인 상황에서 가장 적은 비용을 지불해야 한다

  • 4
  • 그리고 이동은 간단합니다. 4

  • ⎧⎩⎨dp[i][1][k]=mint∈[x,y](dp[i−1][t][k⊕1]) ,j=1dp[i][j][k]=dp[i−1][j−1][k] ,j≠1
    4
  • 마지막 답은 뽑는 거예요.
    mini∈[x,y](min(dp[m][i][0],dp[m][i][1]))


  • AC 코드:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define MAX 1007
    
    using namespace std;
    
    char a[MAX][MAX];
    int b[MAX],w[MAX],dp[MAX][MAX][2],n,m,x,y;
    
    int main ( )
    {
        while ( ~scanf ( "%d%d%d%d" , &n , &m , &x , &y ))
        {
            for ( int i = 1 ; i <= n ; i++ )
                scanf ( "%s" , a[i]+1 );
            for ( int i = 1 ; i <= m ; i++ )
            {
                b[i] = w[i] = 0;
                for ( int j = 1 ; j <= n ; j++ )
                    if ( a[j][i] == '#' ) w[i]++;
                    else b[i]++;
            }
            memset ( dp , 0x3f , sizeof ( dp ));
            const int INF = dp[0][0][0];
            dp[1][1][0] = b[1];
            dp[1][1][1] = w[1];
            for ( int i = 2; i <= m ; i++ )
            {
                for ( int j = x ; j <= y ; j++ )
                {
                    if ( dp[i-1][j][1] != INF )
                        dp[i][1][0] = min ( dp[i][1][0] , dp[i-1][j][1] + b[i] );
                    if ( dp[i-1][j][1] != INF )
                        dp[i][1][1] = min ( dp[i][1][1] , dp[i-1][j][0] + w[i] );
                }
                for ( int j = 2; j <= y ; j++ )
                {
                    if ( dp[i-1][j-1][0] != INF )
                        dp[i][j][0] = dp[i-1][j-1][0] + b[i];
                    if ( dp[i-1][j-1][1] != INF )
                        dp[i][j][1] = dp[i-1][j-1][1] + w[i];
                }
            }
            int ans = INF;
            for ( int i = x ; i <= y ; i++ )
            {
                ans = min ( ans , dp[m][i][0] );
                ans = min ( ans , dp[m][i][1] );
            }
            printf ( "%d
    "
    , ans ); } }

    좋은 웹페이지 즐겨찾기