uva 1631——Locker

叁歲伎倆 2022-08-18 11:31 25阅读 0赞

题意：有一个n位的密码锁，每位都是0——9可以循环旋转，每次可以往上或者往下旋转一下，然后给定初始状态和末状态求最小旋转步数。

思路：递推，dp（i，x，y）表示翻到i位第i+1位为x，第i+2位为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 i=s;i<=t;i++)
    const int N=12,M=1005;
    
    char s[M],t[M];
    int a[M],b[M];
    int dp[M][N][N];
    
    int main()
    {
        while (~scanf("%s %s",s,t)){
            int n=strlen(s);
            ft(i,1,n) a[i]=s[i-1]-'0',b[i]=t[i-1]-'0';
            a[n+1]=b[n+1]=a[n+2]=b[n+2]=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]-x+10)%10;
                ft(j,0,d) ft(k,0,j)
                dp[i][(y+j)%10][(a[i+2]+k)%10]=min(dp[i][(y+j)%10][(a[i+2]+k)%10],dp[i-1][x][y]+d);
                int p=10-d;
                ft(j,0,p) ft(k,0,j)
              dp[i][(y-j+10)%10][(a[i+2]-k+10)%10]=min(dp[i][(y-j+10)%10][(a[i+2]-k+10)%10],dp[i-1][x][y]+p);
            }
            printf("%d\n",dp[n][0][0]);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关 SWUST OJ 480: Locker doors

题目描述 There are n lockers in a hallway numbered sequentially from 1 to n. Initially, al

红太狼/ 2024年04月01日 09:41/ 0 赞/ 200 阅读

相关 LeetCode_dijkstra算法_中等_1631. 最小体力消耗路径

目录 1.题目 2.思路 3.代码实现（Java） 1.题目你准备参加一场远足活动。给你一个二维 rows \ columns 的地图 hei

约定不等于承诺〃/ 2023年10月06日 22:37/ 0 赞/ 137 阅读

相关 P1631-序列合并

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 08:55/ 0 赞/ 65 阅读

相关 activemq Lease Database Locker

[http://activemq.apache.org/pluggable-storage-lockers.html][http_activemq.apache.org_plu

拼搏现实的明天。/ 2023年05月29日 06:53/ 0 赞/ 91 阅读

相关 Leetcode1631最小体力消耗路径--三种思路

Leetcode1634最小体力消耗路径思路一、暴力(回溯法) 说明:此方法时间复杂度太大,不能通过测试,仅仅作为参考 class Solution {

Love The Way You Lie/ 2022年10月24日 06:05/ 0 赞/ 188 阅读

相关 uva 1631——Locker

题意：有一个n位的密码锁，每位都是0——9可以循环旋转，每次可以往上或者往下旋转一下，然后给定初始状态和末状态求最小旋转步数。思路：递推，dp（i，x，y）表示翻

叁歲伎倆/ 2022年08月18日 11:31/ 0 赞/ 26 阅读

相关 poj-1631Bridging signals(LIS)

Bridging signals <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

逃离我推掉我的手/ 2022年08月10日 00:44/ 0 赞/ 216 阅读

相关 poj 1631Bridging signals Dp（最长递增子序列）

Bridging signals <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

古城微笑少年丶/ 2022年04月01日 08:54/ 0 赞/ 246 阅读

相关 HRBUST-1631.技能修炼(拓扑排序)

[HRBUST-1631.技能修炼][HRBUST-1631.] Description 寒假第三次周赛强势袭来，首先祝愿大能依靠自己所学的取得一个好成绩。学习之余

╰半橙微兮°/ 2022年02月13日 08:53/ 0 赞/ 232 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 381 阅读