[문제풀이] 낙곡 2704 포병 진지(NOI 2001)

이 문제는 상압 dp의 특별 독종의 기초 문제(아침 내내 쳤지만)이지만 포병마다 그 다음 두 줄의 방치에 영향을 미치기 때문에 상으로 두 줄을 눌러 각 줄의 상황을 처리하면 된다.한 줄 한 줄을 놓을 때도 간단하다. 이 위치 앞의 두 줄에 포병이 놓여 있는지 없는지, 그리고 이 위치가 언덕인지 아닌지만 고려하면 된다.
그러면 먼저 dp방정식은 빨리 추측할 수 있다. dp[L][S][i]는 현재 상태가 S이고 이전 줄의 상태가 L임을 나타낸다. 현재 i줄을 고려했다.
dp[L][S][i]=max(dp[L][S][i],dp[FL][L][i-1]+Sum[S]); 여기서 FL은 상단의 상태를 나타내고 Sum[S]는 현재 상태 S에 1이 포함되어 있음을 나타냅니다.
그러면 이 dp방정식이 생기면 즐겁게 전달할 수 있지만 이 문제는 몇 가지 세부 사항이 있으니 주의해야 한다.
1. 위치마다 언덕인지 아닌지 판단
이것은 아주 잘 해결된다. 한 줄의 입력을 모두 2진수(평원은 0이고 언덕은 1)로 바꾸고 판단을 기다리는 상태와 직접 비트 연산을 하면 된다. 바로 S&a[i]이다. 비트 연산 결과가 0이 아니라면 어떤 위치가 언덕 위에 놓여 있다는 것이다. 즉, 현재 상태가 비합법적이라는 것이다.
2. 각 상태에 포병 두 명이 있는지 좌우 거리가 두 칸 이내인지 판단
이것은 머리를 써서 생각해 보면 우리는 신기한 결론을 발견할 수 있다. 만약에 현재 상태를 나타내는 2진수 비트 연산을 왼쪽으로 한 번 옮기면 이 결과와 원래 상태로 비트 연산과 조작을 한 번 한다. 만약에 결과가 0이 아니라면 반드시 두 포병의 왼쪽 오른쪽 거리가 한 칸 안에 존재할 것이다.같은 이치로 왼쪽으로 두 자리를 옮기면 좌우 거리가 두 칸 안에 있다는 것을 판단할 수 있다.이 과정은 바로 S&(S<<1), S&(S<2)이다.
3. 각 열마다 포병이 있는지 없는지 판단
이것은 바로 현재 상태로 이전의 두 줄과 나누면 된다. 바로 S&L, S&FL이다. 만약에 조작 결과와 0이 되지 않는다면 몇몇 열의 앞줄에 포병이 있다는 것을 의미한다. 즉, 현재 상태가 합법적이지 않다는 것이다.
마지막으로 말하자면, 반드시 스크롤 그룹을 사용해야 한다. (한 줄과 두 줄만 사용하기 때문에 세 줄만 스크롤해야 한다.) 그렇지 않으면 MLE 0이 될 것이다. (나는 애초에 이렇게 비참했다.)
자, 세부 사항은 모두 말했습니다. 다음은 구체적인 코드가 실현되었습니다.

#include
using namespace std;
int n,m,ans,dp[(1<<10)][(1<<10)][3]/*    */,a[105],Sum[(1<<10)];
char x;
int getsum(int S)   //     S        1
{
    int tot=0;
    while(S) {if(S&1) tot++; S>>=1;}
    return tot;
}
int main()
{
    cin>>n>>m;
    for(int i=0;ifor(int j=0;jcin>>x,a[i]<<=1,a[i]+=(x=='H'?1:0); //      
    for(int i=0;i1<//    Sum   
    for(int S=0;S1<if(!(S&a[0] || (S&(S<<1)) || (S&(S<<2))))
            dp[0][S][0]=Sum[S]; //   
    for(int L=0;L1<for(int S=0;S1<if(!(L&S || L&a[0] || S&a[1] || (L&(L<<1)) || (L&(L<<2)) || (S&(S<<1)) || (S&(S<<2))))  //       
                dp[L][S][1]=Sum[S]+Sum[L];
    for(int i=2;ifor(int L=0;L1<if(L&a[i-1] || (L&(L<<1)) || (L&(L<<2))) continue;  //  
            for(int S=0;S1<if(S&a[i] || L&S || (S&(S<<1)) || (S&(S<<2))) continue; //    
                for(int FL=0;FL1<if(FL&L || FL&S || FL&a[i-2] || (FL&(FL<<1)) || (FL&(FL<<2)))   continue;   //     
                    dp[L][S][i%3]=max(dp[L][S][i%3],dp[FL][L][(i-1)%3]+Sum[S]);     //         
                }
            }
        }
    for(int L=0;L1<for(int S=0;S1<1)%3]); //                
    cout<return 0;
}