云南 网站建立,word和wordpress,百度手机网站优化,建站大师排名表2021题意#xff1a;有一个n位的密码锁#xff0c;每位都是0——9可以循环旋转#xff0c;每次可以往上或者往下旋转一下#xff0c;然后给定初始状态和末状态求最小旋转步数。 思路#xff1a;递推#xff0c;dp#xff08;i#xff0c;x#xff0c;y#xff09;表示翻到…题意有一个n位的密码锁每位都是0——9可以循环旋转每次可以往上或者往下旋转一下然后给定初始状态和末状态求最小旋转步数。 思路递推dpixy表示翻到i位第i1位为x第i2位为y的最小步数枚举上翻状态找到正翻和倒翻的最小值。 code #include bits/stdc.h
using namespace std;#define cls(a,c) memset(a,c,sizeof (a))
#define ft(i,s,t) for (int is;it;i)
const int N12,M1005;char s[M],t[M];
int a[M],b[M];
int dp[M][N][N];int main()
{while (~scanf(%s %s,s,t)){int nstrlen(s);ft(i,1,n) a[i]s[i-1]-0,b[i]t[i-1]-0;a[n1]b[n1]a[n2]b[n2]0;cls(dp,63);//ft(i,1,n) printf(%d,b[i]);dp[0][a[1]][a[2]]0;ft(i,1,n) ft(x,0,9) ft(y,0,9){int d(b[i]-x10)%10;ft(j,0,d) ft(k,0,j)dp[i][(yj)%10][(a[i2]k)%10]min(dp[i][(yj)%10][(a[i2]k)%10],dp[i-1][x][y]d);int p10-d;ft(j,0,p) ft(k,0,j)dp[i][(y-j10)%10][(a[i2]-k10)%10]min(dp[i][(y-j10)%10][(a[i2]-k10)%10],dp[i-1][x][y]p);}printf(%d\n,dp[n][0][0]);}
}
