HDOJ 4433 locker

locker

Time Limit: 3000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 4433
64-bit integer IO format: %I64d Java class name: Main

Type:

None Graph Theory 2-SAT Articulation/Bridge/Biconnected Component Cycles/Topological Sorting/Strongly Connected Component Shortest Path Bellman Ford Dijkstra/Floyd Warshall Euler Trail/Circuit Heavy-Light Decomposition Minimum Spanning Tree Stable Marriage Problem Trees Directed Minimum Spanning Tree Flow/Matching Graph Matching Bipartite Matching Hopcroft–Karp Bipartite Matching Weighted Bipartite Matching/Hungarian Algorithm Flow Max Flow/Min Cut Min Cost Max Flow DFS-like Backtracking with Pruning/Branch and Bound Basic Recursion IDA* Search Parsing/Grammar Breadth First Search/Depth First Search Advanced Search Techniques Binary Search/Bisection Ternary Search Geometry Basic Geometry Computational Geometry Convex Hull Pick's Theorem Game Theory Green Hackenbush/Colon Principle/Fusion Principle Nim Sprague-Grundy Number Matrix Gaussian Elimination Matrix Exponentiation Data Structures Basic Data Structures Binary Indexed Tree Binary Search Tree Hashing Orthogonal Range Search Range Minimum Query/Lowest Common Ancestor Segment Tree/Interval Tree Trie Tree Sorting Disjoint Set String Aho Corasick Knuth-Morris-Pratt Suffix Array/Suffix Tree Math Basic Math Big Integer Arithmetic Number Theory Chinese Remainder Theorem Extended Euclid Inclusion/Exclusion Modular Arithmetic Combinatorics Group Theory/Burnside's lemma Counting Probability/Expected Value Others Tricky Hardest Unusual Brute Force Implementation Constructive Algorithms Two Pointer Bitmask Beginner Discrete Logarithm/Shank's Baby-step Giant-step Algorithm Greedy Divide and Conquer Dynamic Programming

A password locker with N digits, each digit can be rotated to 0-9 circularly.
You can rotate 1-3 consecutive digits up or down in one step.
For examples:
567890 -> 567901 (by rotating the last 3 digits up)
000000 -> 000900 (by rotating the 4th digit down)
Given the current state and the secret password, what is the minimum amount of steps you have to rotate the locker in order to get from current state to the secret password?

Input

Multiple (less than 50) cases, process to EOF.
For each case, two strings with equal length (≤ 1000) consists of only digits are given, representing the current state and the secret password, respectively.

Output

For each case, output one integer, the minimum amount of steps from the current state to the secret password.

Sample Input

111111 222222
896521 183995

Sample Output

2
12

Source

2012 Asia Tianjin Regional Contest

Submit Status Statistics Discuss

注意：在第一个字符之前加一个‘0’，在末尾加两个'0'

dp[x][y]表示前i个字符已经调整好，并且第[i+1]为x，[i+2]为y，此状态最少需要的调整次数。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char s1[1010],s2[1010];
    int a[1110],b[1110];
    int dp[1110][10][10];

while(cin>>s1>>s2)
{
    int n=strlen(s1);

    memset(a,0,sizeof(a)); memset(b,0,sizeof(b));

    for(int i=1;i<=n;i++)
    {
        a=s1[i-1]-'0'; b=s2[i-1]-'0';
    }

    memset(dp,63,sizeof(dp));
    dp[0][a[1]][a[2]]=0;

    for(int i=1;i<=n;i++)
    {
        for(int x=0;x<10;x++)
        {
            for(int y=0;y<10;y++)
            {
                int up=(b-x+10)%10;
                for(int j=0;j<=up;j++)
                    for(int k=0;k<=j;k++)
                    dp[(y+j)%10][(a[i+2]+k)%10]=min(dp[i-1][x][y]+up,dp[(y+j)%10][(a[i+2]+k)%10]);
                int down=10-up;
                for(int j=0;j<=down;j++)
                    for(int k=0;k<=j;k++)
                    dp[(y-j+10)%10][(a[i+2]-k+10)%10]=min(dp[i-1][x][y]+down,dp[(y-j+10)%10][(a[i+2]-k+10)%10]);
            }
        }
    }
    cout<<dp[n][0][0]<<endl;
}

    return 0;
}

* This source code was highlighted by YcdoiT. ( style: Vs )