[HDU 4433]locker[DP]

제목:
비밀번호가 만들어진 현황과 비밀번호를 제시하고, 매번 연속된 최대 3열을 이동할 수 있으며, 위로 이동하거나 아래로 이동하여 비밀번호를 빼내는 데 필요한 최소 걸음수를 구할 수 있다.
아이디어:
우선 회복 과정에서 한 분 한 분의 시간 순서를 조정하는 것은 영향을 주지 않으므로 왼쪽에서 오른쪽으로 제거하는 것도 무방하다.
pp[i][x][y]는 앞의 i위가 0으로 제거되었고 그 뒤의 두 자리가 x, y일 때 필요한 최소 조작수를 나타낸다.
매번 1~3위를 회전할 수 있으니 3위를 회전할 때 3위와 2위의 구속 관계를 주의해야 한다.[그래서 와...]
Wordstack 문제의'문제풀이판'과 같은 사고방식으로 이미 알고 있는 상태로 미지의 상태를 업데이트합니다.
 
 

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 1005;

const int INF = 0x3f3f3f3f;

int dp[MAXN][10][10], bit[MAXN], n;

char s[MAXN], t[MAXN];

int main()

{

    while(~scanf("%s %s",s,t))

    {

        n = strlen(s);

        for(int i=0;i<n;i++)

            bit[i+1] = (t[i]+10-s[i]) % 10;

        bit[n+1] = bit[n+2] = 0;

        memset(dp,0x3f,sizeof(dp));

        dp[0][bit[1]][bit[2]] = 0;

        for(int i=0;i<n;i++)

            for(int x=0;x<10;x++)

                for(int y=0;y<10;y++)

                    if(dp[i][x][y]!=INF)

                    {

                        dp[i+1][y][bit[i+3]]

                         = min(dp[i+1][y][bit[i+3]],

                               dp[i][x][y] + min(x,10-x));//1

                        for(int j=1;j<=x;j++)

                        {

                            dp[i+1][(y+10-j)%10][bit[i+3]]

                             = min(dp[i+1][(y+10-j)%10][bit[i+3]],

                                   dp[i][x][y] + x);//2

                            for(int k=1;k<=j;k++)

                                dp[i+1][(y+10-j)%10][(bit[i+3]+10-k)%10]

                                 = min(dp[i+1][(y+10-j)%10]

                                         [(bit[i+3]+10-k)%10],

                                       dp[i][x][y] + x);

                        }

                        for(int j=1;j<=10-x;j++)

                        {

                            dp[i+1][(y+j)%10][bit[i+3]]

                             = min(dp[i+1][(y+j)%10][bit[i+3]],

                                   dp[i][x][y] + 10-x);//2

                            for(int k=1;k<=j;k++)

                                dp[i+1][(y+j)%10][(bit[i+3]+k)%10]

                                 = min(dp[i+1][(y+j)%10][(bit[i+3]+k)%10],

                                       dp[i][x][y] + 10-x);

                        }

                    }

        printf("%d
",dp[n][0][0]);

    }

}

 
그나저나이것은 팀을 구성한 이래 내가 만든 첫 번째 비수문제인데......나한테 비수제지..
 
DP는 그래도 재밌어요. 많이 연습하세요~ orz