100 개 동적 계획 - 27 POJ 1185 포병 진지 상태 압축, 예처리, 스크롤 그룹

상태 압축을 잘 못해요. 하나 배워요.
정의상태 dp[row][i][j]는 현재 제row행을 고려하고 있음을 나타낸다. 이 행의 상태가 i이고 이전 행의 상태가 j일 때 배치할 수 있는 최대 포병 수량을 나타낸다.
상태 이동 방정식은 dp[row][i][j]=max(dp[row][i][j], dp[row-1][j][k]+num[i])이다. 그 중에서num[i]는 상태 i의 포병 수를 나타낸다.
이렇게 보기에도 어렵지 않은데, 오랫동안 상태가 압축된 DP를 쓰지 못했으니, 이 문제와 이전에 썼던 상압 DP의 공통점과 차이점을 잘 회상해 보아야 한다.
상태 이동 방정식을 통해 알 수 있듯이 이 dp는 스크롤 그룹으로 최적화할 수 있다
나는 하나의 예처리를 통해 먼저 같은 줄의 합법적인 상호 상태를 보증한 후에 상태 수가 크게 감소한 것을 발견했는데 실제로는 88개밖에 없었다
한 상태에 몇 명의 포병이 있는지 판단하는 데 있어서, 내 블로그에 2진법 1의 개수를 구해서 직접 가져와서 쓰면 된다고 했다http://blog.csdn.net/good_night_sion_/article/details/53148718
다음은 코드입니다.

#include 
#include 
#include 

using namespace std;

int board[105],n,m,ans,limi,dp[2][100][100],t;
inline int count_bits(int x);
vector state;
char c;
void pretreatment();

int main(){
    ios_base::sync_with_stdio(false);
    pretreatment();
    while(cin>>n>>m){
        if(n==0){
            cout<<0<>c;
            if(c=='H')
                board[i]|=(1<=2){
            t^=1;
            for(int i=0;state[i]=3){
            t^=1;
            for(int row=3;row<=n;++row){
                for(int i=0;state[i]>1))&&!(i&(i>>2)))
        state.push_back(i);
}

inline int count_bits(int x){
    x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
    x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
    x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
    x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
    x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
    return x;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

100가지 동적 계획 – 42 CodeForces 908D New Year and Original Order 확률 DP

k,pa,pb 하나 주세요. 처음에 현재 직렬은 빈 직렬로 매번 조작할 때pa/(pa+pb)의 확률로 현재 직렬에'a', pb/(oa+pb)의 확률에 문자 b를 추가한다. 현재 직렬의 하위 서열을 고려하면 k 하위 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

100 개 동적 계획 - 27 POJ 1185 포병 진지 상태 압축, 예처리, 스크롤 그룹

좋은 웹페이지 즐겨찾기