여동생 사랑 수열 (동적 계획 dp)

제목 링크: 소 매 사랑 수열
출처: 우 객 망 시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K 64bit IO Format:% lld
제목 설명: 우 매 는 수열 을 하고 있 습 니 다. 그의 손 에 길이 가 n 인 서열 a 가 있 습 니 다. 이것 이 01 서열 임 을 보증 하고 다음 과 같은 두 가지 조작 을 수행 합 니 다. 1. 한 가지 수정: 위치 x 의 수 를 뒤 집 습 니 다 (0 변 1, 1 변 0).2. 접두사 수정: 위치 1 ~ x 의 수 를 뒤 집 습 니 다.그 는 이제 뒤 집기 횟수 를 최소 화하 여 수열 의 모든 수 를 0 으로 바 꾸 려 고 한다.
입력 설명: 첫 줄, 숫자 n 을 입력 하 십시오.두 번 째 줄, n 개 수 를 입력 하고, i 개 수 는 ai 를 표시 합 니 다.
출력 설명: 출력 최소 반전 횟수.
예제 1 입력 10 1 0 1 0 0 1 0 0 0 0
출력
샘플 설명: 첫 번 째 사용 (1) 조작, 2 변경: 1, 1, 1, 0, 0, 0, 1, 0 두 번 째 사용 (2) 조작, 1 - 4 를 모두 변경: 0, 0, 0, 0, 0, 0, 0 세 번 째 사용 (1) 조작, 8 변경: 0, 0, 0, 0, 0 0, 0, 0 비고: 데이터 보증 1 < = n < = 10 ^ 5, 0 < = ai < = 1.
제목: 모든 수 를 0 의 최소 반전 수로 바 꾸 는 것 이다.사고방식: 바로 dp 의 관건 은 상태 전이 방정식 을 쓰 는 것 이다.
dp [i] [0] 은 [1, i] 를 모두 0 으로 뒤 집 는 데 필요 한 최소 뒤 집기 횟수 dp [i] [1] 을 나타 낸다.
a [ i ] = = 1 { d p [ i ] [ 0 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] + 1 ) ; d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] ) ; a[i] == 1\begin{cases} dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1); \\ \\ dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]); \end{cases} a[i]==1⎩⎪⎨⎪⎧​dp[i][0]=min(dp[i−1][0]+1,dp[i−1][1]+1);dp[i][1]=min(dp[i−1][0]+1,dp[i−1][1]);​
dpi] [0] = min ([1, i - 1] 구간 을 0 으로 바 꾸 는 최소 횟수 에 a [i] 이 1 을 0 으로 바 꾸 는 이 단 계 를 더 하면 [1, i - 1] 구간 을 1 로 바 꾸 는 최소 횟수 (이때 [1, i] 구간 은 모두 1) 를 더 한 다음 [1, i] 이 구간 을 뒤 집 고 횟수 에 1) dp [1] = min ([1, i - 1] 을 0 으로 바 꾸 는 최소 횟수, 그리고 나 는 [1, i - 1] 구간 을 한 걸음 더 뒤 집 었 다. 왜냐하면 a [i]1 이기 때문에 이때 [1, i] 는 모두 1 이다. a [i] 가 1 이기 때문에 횟수 는 [1, i - 1] 을 1 로 뒤 집 는 횟수 와 같다)
사실 a [i] = = 0 의 상태 전이 방정식 은 위의 사상 과 마찬가지 로 잘 이해 하기 위해 서 다시 한 번 말씀 드 리 겠 습 니 다.
만약 a [i] = = 0, 상태 전이 방정식:
a [ i ] = = 0 { d p [ i ] [ 0 ] = m i n ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + 1 ) ; d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] + 1 ) ; a[i] == 0\begin{cases} dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1); \\ \\ dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1); \end{cases} a[i]==0⎩⎪⎨⎪⎧​dp[i][0]=min(dp[i−1][0],dp[i−1][1]+1);dp[i][1]=min(dp[i−1][0]+1,dp[i−1][1]+1);​
dpi] [0] = min (a [i] = 0 이기 때문에 구간 [1, i - 1] 을 0 으로 뒤 집 는 횟수 와 같 습 니 다. 구간 [1, i - 1] 을 1 로 뒤 집 는 횟수 가 한 걸음 더 많 습 니 다. 구간 [1, i - 1] 을 전체적으로 뒤 집 으 면 [1, i] 가 모두 0 입 니 다. dp [1] = min (구간 [1, i - 1] 을 0 으로 뒤 집 으 면 [1, i] 가 모두 0 입 니 다. 그리고 구간 [1, i] 을 뒤 집 으 면 모두 1 이 됩 니 다. 구간 [1, i - 1]1 로 넘 기 는 걸음 수 에 a [i] 이 0 을 1 로 넘 기 는 이 걸음)
마지막 출력 구간 [0, n] 은 모두 0 의 최 하 횟수, 즉 dp [n, 0] 로 바 뀌 면 된다.
코드:

#include
using namespace std;
const int maxn=1e5+5;
int dp[maxn][2],a[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]) // a[i] == 1
            {
                dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);  
                dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]);  
            }
            else  // a[i] == 0
            {
                dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
                dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);
                
            }
        }
        cout<<dp[n][0]<<endl;

    }
    return 0;
}

화 이 팅!
공동 노력!
Keafmd
본인 블 로그