首页 > 代码库 > HDU4433locker【dp】
HDU4433locker【dp】
locker
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1481 Accepted Submission(s): 654
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?
For each case, two strings with equal length (≤ 1000) consists of only digits are given, representing the current state and the secret password, respectively.
大意：这个题是去年亚洲区的一个题 题意很简单：就是告诉你一个有n位数的密码锁（n<=1000)，然后问最少通过多少步操作能得到正确的结果
操作的内容是：每次可以选择连续的一个两个或者三个数字进行旋转数字从0到9然后又循环到0
这个题还是比较好的 我觉得还是蛮有意思的
dp[i][j][k]表示前i位已经匹配第i+1位为j 第i+2位为k的最少步数
比如 1 1 1 1 1 1
2 2 2 2 2 2
dp[3][4][5] 所表示的状态就是
0 2 2 4 5
0 2 2 2 2 2 2
不难发现只要每次都把i-1的j和k枚举一遍 再将其全部转移到第i种状态之下就可以了
转移过程中遇到两个问题
一是如何把转以后的状态如何表示出来 一是转移的步数是多少
对于第一个问题
假如i - 1的dp为dp[i-1][j][k]
那么此时前i-1位已经完全匹配 现在就是把j变成b[i]可以确定正转和反转各有多少步
那么对于dp[i][j2][k2] 原来的k变成了现在的j2 原来的a[i + 2]变成了现在的k2
至于转移的步数这么考虑
只要是旋转那么一定是第i位旋转的合适的位置 假如说需要t步
那么经过t步之后 i+1位的旋转步数t2一定<= t 而i+2位的旋转步数t2一定小于t1
也就是说旋转t步得到的状态可以由上一种状态旋转t步得到
也就是转移的步数就是t步
以上这个问题就全部解决
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 1010; 7 const int INF = 1000000000; 8 int dp[maxn][10][10]; 9 char s1[maxn], s2[maxn];10 int a[maxn], b[maxn];11 int up[10][10], dw[10][10];12 13 int main() {14 for(int i = 0; i < 10; i++) {15 for(int j = 0; j < 10; j++) {16 up[i][j] = j >= i ? j - i : ( 9 - i ) + ( j + 1 );17 dw[i][j] = i >= j ? i - j : ( i ) + ( 9 - j + 1);18 }19 }20 while(EOF != scanf("%s%s",s1, s2) ) {21 int n = strlen(s1);22 a[0] = b[0] = 0;23 for(int i = 0; i < n; i++) {24 a[i + 1] = s1[i] - ‘0‘;25 b[i + 1] = s2[i] - ‘0‘;26 }27 a[n + 1] = a[n + 2] = 0; b[n + 1] = b[n + 2] = 0;28 memset(dp, 0x3f, sizeof(dp));29 dp[0][a[1]][a[2]] = 0;30 for(int i = 1; i <= n; i++) {31 for(int j = 0; j < 10; j++) {32 for(int k = 0; k < 10; k++) {33 int t1 = up[j][b[i]];34 for(int x = 0; x <= t1; x++) {35 for(int y = 0; y <= x; y++) {36 dp[i][(k + x) % 10][(a[i + 2] + y) % 10] = min(dp[i][(k + x) % 10][(a[i + 2] + y) % 10], dp[i - 1][j][k] + t1);37 }38 }39 int t2 = dw[j][b[i]];40 for(int x = 0; x <= t2; x++) {41 for(int y = 0; y <= x; y++) {42 dp[i][(k - x + 20) % 10][(a[i + 2] - y + 20) % 10] = min(dp[i][(k - x + 20) % 10][(a[i + 2] - y + 20) % 10], dp[i -1][j][k] + t2);43 }44 }45 }46 }47 }48 int ans = INF;49 for(int i = 0; i < 10; i++) {50 for(int j = 0; j < 10; j++) {51 ans = min(ans, dp[n][i][j]);52 }53 } 54 printf("%d\n", ans);55 }56 return 0;57 }
HDU4433locker【dp】