题目链接
1.首先如果只转动一位，那么不难发现每一位是互不影响的。而本题可以同时最多转动三位。那么我们不难发现，因为第二位第三位什么决策最优是未知的，但是当前位最少的转动次数是一定的（要么向上要么向下）。在将第一位转动到正确位置的过程中，第二位第三位可以转也可以不转，那么我们需要枚举所有的情况进行状态转移
2.然后观察上图，原位置设为 a a a，目标未知设为 b b b，因为二者的大小关系是不确定的，但是一共只有十位，因此我们无需分类讨论，只需使用取模的技巧：
若向上转，则需要 u = ( b [ c u r ] + 10 − x ) u=(b[cur]+10-x)%10 u=(b[cur]+10−x)次，此时因为是向上转动，后面两位只需 ( y + i ) (y+i)%10 (y+i)若向下转，则需要 d = ( x + 10 − b [ c u r ] ) d=(x+10-b[cur])%10 d=(x+10−b[cur])次，此时因为是向下转动，那么后面两位需要 ( y + 10 − i ) (y+10-i)%10 (y+10−i) #include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=2e5+10; string s1,s2; int n; int a[1010],b[1010]; int d[1010][11][11][11]; int dp(int cur,int x,int y,int z){ if(cur>=n) return 0; int &ans=d[cur][x][y][z]; if(ans!=-1) return ans; ans=inf; int u=(b[cur]+10-x)%10,d=(x+10-b[cur])%10; //注意这里是x，而不是a[cur] for(int i=0;i<=u;i++) for(int j=0;j<=i;j++) ans=min(ans,dp(cur+1,(y+i)%10,(z+j)%10,a[cur+3])+u); for(int i=0;i<=d;i++) for(int j=0;j<=i;j++) ans=min(ans,dp(cur+1,(y+10-i)%10,(z+10-j)%10,a[cur+3])+d); return ans; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>s1>>s2){ n=s1.size(); for(int i=0;i<n;i++) a[i]=s1[i]-'0'; for(int i=0;i<n;i++) b[i]=s2[i]-'0'; memset(d,-1,sizeof d); cout<<dp(0,a[0],a[1],a[2])<<endl; } return 0; }