icontofig | 发布于 2019-08-09 17:40:23 | 阅读量 372 | DP 最短路
发布于 2019-08-09 17:40:23 | DP 最短路

题目大意

 给你一个数字串,问你如果一步只能跳i或j(0≤i,j≤9)的话,跳到x‘ % 10,需要至少添加多少数字进入这个串中,使得添加数字后的串是可能通过每次跳i或者j构造出来的。

题解

这绝对算一个好题。

首先我们看这个跳法,每一次跳都只能跳到当前数+x 对10取模,所以相当于我们在10的完全剩余系里面疯狂跳。

然后注意到其实我们从当前数要跳到数字串中的下一个数的时候,数字串每两个数之间的跳法是互不影响的。于是我们对于数字串每两个数之间也就是求最短路处理。

我们设mp[i][j][x][y]表示从x跳到y,只能一次性跳i或者j的最短距离,然后对于10×10的方阵,直接用Floyd预处理出来。

然后我们进入数字串直接扫一遍,如果下一个与当前位置最短路为INF,直接输出-1,否则答案就加上两个之间的最短距离-1.

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
string s;
int len = 0;
int mp[10][10][10][10];
long long ans = 0;
int main(){
    for(int i = 0;i <= 9;++i){
        for(int j = 0;j <= 9;++j){
            for(int k = 0;k <= 9;++k){
                for(int l = 0;l <= 9;++l){
                    mp[i][j][k][l] = INF;
                }
            }
        }
    }
    for(int i = 0;i <= 9;++i){
        for(int j = 0;j <= 9;++j){
            for(int k = 0;k <= 9;++k){
//                if(i != 0)
                    mp[i][j][k][(k+i)%10] = 1;
//                if(j != 0)
                    mp[i][j][k][(k+j)%10] = 1;
            }
            for(int p = 0;p <= 9;++p){
                for(int k = 0;k <= 9;++k){
                    for(int x = 0;x <= 9;++x){
                        mp[i][j][k][x] = min(mp[i][j][k][x],mp[i][j][k][p] + mp[i][j][p][x]);
                    }
                }
            }
        }
    }
    int now,nxt;
    cin >> s;
    len = s.length();
    bool flag = false;
    for(int i = 0;i <= 9;++i){
        for(int j = 0;j <= 9;++j){
            if(len == 1){
                cout << 0 << " ";
                continue;
            }
            ans = 0;
            flag = true;
            for(int k = 0;k < len - 1;++k){
                now = s[k] - '0';
                nxt = s[k+1] - '0';
                if(mp[i][j][now][nxt] == INF){
                    cout << -1 << " ";
                    flag = false;
                    break;
                }
                else ans += mp[i][j][now][nxt] - 1;
            }
            if(!flag)continue;
            cout << ans << " ";
        }
        cout << "\n";
    }
    return 0;
}



内容更新于: 2019-08-09 17:40:53
链接地址: http://blog.leanote.com/post/icontofig/Codeforces-1202

上一篇: 2019 Multi-University Training Contest 7 1006 Final Exam 思维题

下一篇: 2019 Multi-University Training Contest 6 1002 Nonsense Time LIS(O(nlogn)版本)

372 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航