UVa 1631 Locker
题目
◇题目传送门◆（由于UVa太慢，这里提供一个vjudge的链接）
◇题目传送门（vjudge）◆
题目大意
有一个NN位的数字密码锁，每位数字可以在 之间旋转。可以同时旋转一到三个。现给定初始状态和最终状态，求最少旋转次数。
思路
这道题我感觉使用递推来转移似乎很困难，所以我们使用记忆化搜索。
定义状态f[p][i][j][k]f[p][i][j][k]为当前正在复原的位置为pp，位置 上的数为ii，位置 上的数为jj，位置 上的数为kk时的最少旋转次数。
每次搜索时我们有向上和向下两种选择，所以我们要分别计算出两种情况所需的次数。
读题可发现，位置 旋转的次数是总是小于等于位置pp旋转的次数；位置 旋转的次数总是小于等于位置p+1p+1旋转的次数。
但是我们不知道要把位置p+1,p+2p+1,p+2旋转多少次，所以我们再枚举一下旋转次数，搜索一下，就可以得出答案。
正解代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int Maxn=1000;
const int INF=0x3f3f3f3f;int N,a[Maxn+5],b[Maxn+5];
int len;
string s1,s2;
int f[Maxn+5][10][10][10];int DFS(int pos,int x,int y,int z) {if(pos>=len)return 0;int &res=f[pos][x][y][z];if(res!=-1)return res;int ret=INF,t;if(x<=b[pos])t=b[pos]-x;else t=b[pos]+10-x;//计算旋转次数for(int i=0;i<=t;i++)//向上旋转for(int j=0;j<=i;j++)ret=min(ret,DFS(pos+1,(y+i)%10,(z+j)%10,a[pos+3])+t);if(x>=b[pos])t=x-b[pos];else t=x+10-b[pos];for(int i=0;i<=t;i++)//向下旋转for(int j=0;j<=i;j++)ret=min(ret,DFS(pos+1,(y-i+10)%10,(z-j+10)%10,a[pos+3])+t);return res=ret;
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(cin>>s1>>s2) {len=s1.length();for(int i=0;i<len;i++) {a[i]=s1[i]-'0';b[i]=s2[i]-'0';}a[len]=a[len+1]=b[len]=b[len+1]=0;//注意后面两位需要清空memset(f,-1,sizeof f);//记忆化数组清空printf("%d\n",DFS(0,a[0],a[1],a[2]));}return 0;
}