首页 > 试题广场 >

【2021】360编程题回文数变换

[编程题]【2021】360编程题回文数变换

热度指数：721 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

所谓回文数就是一个数字，从左边读和从右边读的结果都是一样的，例如12321。

现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的。

已知增加和删除每个数字的代价如下：

增加一个1，代价：100；删除一个1，代价：120。

增加一个2，代价：200；删除一个2，代价：350。

增加一个3，代价：360；删除一个3，代价：200。

增加一个4，代价：220；删除一个4，代价：320。

请问如何通过最少的代价将一个数字变换为一个回文数。当然，如果一个数字本身已经是一个回文数（包括一位数，例如：2），那么变换的代价为0。

输入描述:

单组输入。

输入一个由1、2、3、4组成的正整数，正整数位数<=100位。【提示：采用字符串输入】

输出描述:

输出一个整数，表示将输入数字变换为一个回文数所需的最少代价。

示例1

输入

输出

说明

增加一个1并增加一个2，将输入正整数变为1223221或者2123212，所需代价最小，为：100+200=300。

算法知识视频讲解

牛客12312341

我又来写题解啦！！！

这是一个区间模型的动态规划！

设f[1][n]为处理区间(1,n)为回文串的最小花费

如果我们处理好 f[i+1][j-1]，区间也就是说,(i+1,j-1)已经是回文的了。

如果ss[i] == ss[j]

则(i,j)区间就是回文的，那么f[i][j]由f[i+1][j-1]直接得来。

如果ss[i] != ss[j]

其实增加一个字符和删除一个字符效果都是一样的，嗯，对吧。

对于区间（i+1，j）处理好的回文区间，我可以增加一个与 s[i]一样的字符，或者将其删掉，看那个花费最小。

对于区间（i，j-1）处理好的回文区间，我可以增加一个与 s[j]一样的字符，或者将其删掉，看那个花费最小。

于是转移方程很明显了

f[i][j]=min{ f[i+1][j]+min(删掉s[i]的代价,增加s[i]的代价) ，f[i][j-1]+min(删掉s[j]的代价,增加s[j]的代价) }

#include<bits/stdc++.h>
 
using namespace std;
 
const int N=110;
 
int f[N][N];
const int a[]={0,100,200,360,220};//增加的代价
const int b[]={0,120,350,200,320};//删除的代价
char ss[N];
 
int main(){
    cin>>ss+1;
    int n=strlen(ss+1);
    for(int i=n-1;i;i--){
        for(int j=i+1;j<=n;j++){
            if(ss[i]==ss[j])
                f[i][j]=f[i+1][j-1];
            else{
                f[i][j]=min(f[i+1][j]+min(a[ss[i]-'0'],b[ss[i]-'0']),f[i][j-1]+min(a[ss[j]-'0'],b[ss[j]-'0']));
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

发表于 2021-05-11 02:05:10 回复(0)

pein531

动态规划，dp[i][j]表示使数字子串num[i~j]为回文串的最小花费，从长度为2的回文串开始考察

(1) 当num[i]=num[j]时，dp[i][j] = dp[i+1][j-1]。

(2) 当num[i]≠num[j]时，就要考察是num[i+1~j]加减一个字符花费小还是num[i~j-1]加减一个字符花费小，选择花费最小的方案即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int[] addCost = new int[]{0, 100, 200, 360, 220};
    static int[] deleteCost = new int[]{0, 120, 350, 200, 320};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] num = br.readLine().trim().toCharArray();
        int n = num.length;
        int[][] dp = new int[n][n];
        for(int L = 2; L <= n; L++){
            for(int i = 0; i < n; i++){
                int j = i + L - 1;
                if(j >= n) break;
                if(num[i] == num[j]){
                    dp[i][j] = dp[i + 1][j - 1];
                }else{
                    dp[i][j] = Math.min(
                        Math.min(dp[i + 1][j] + addCost[num[i] - '0'], dp[i + 1][j] + deleteCost[num[i] - '0']),
                        Math.min(dp[i][j - 1] + addCost[num[j] - '0'], dp[i][j - 1] + deleteCost[num[j] - '0'])
                    );
                }
            }
        }
        System.out.println(dp[0][n - 1]);
    }
}

发表于 2021-08-22 23:14:19 回复(0)

牛客256183608号

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        char[] str = sc.nextLine().toCharArray();
        int len = str.length;
        //dp[i][j]代表str[i....j]变换为回文串的代价
        int[][] dp = new int[len][len];
        //添加 删除的代价
        int[] add = {0,100,200,360,220};
        int[] delete = {0,120,350,200,320};
        //遍历区间长度从2开始 长度为1的全是回文默认为0
        for(int L = 2; L <= len; L++){
        //遍历左端点
            for(int i = 0; i < len; i++){
                //右端点
                int j = i + L - 1;
                //右端越界退出此次长度循环
                if(j >= len) break;
                if(str[i] == str[j]){
                    //长度为2时使用初始值0
                    if(L > 2){
                        dp[i][j] = dp[i+1][j-1];
                    }
                }else{
                    //dp[i+1][l] 右边添加一个str[i]或者左边删除
                    //dp[i][l-1] 左边添加一个str[j]或者右边删除
                    dp[i][j] = Math.min(
                    dp[i+1][j]+Math.min(add[str[i]-'0'],delete[str[i]-'0']),
                    dp[i][j-1]+Math.min(add[str[j]-'0'],delete[str[j]-'0'])
                    );
                }
            }
        }
        System.out.println(dp[0][len-1]);
    }
}

发表于 2021-07-14 22:50:27 回复(2)

不想上班艾伦是单身

添加一个画蛇添足的python版本，我想复杂了，先递归找到了最小的非回文字符串，然后求和计算，结果就是最后一个样例因为内存炸了找了半天。其实只要注意怎么判断回文就很简单

string = input()
length = len(string)
def gen_back_txt(string):
add = [100,200,360,220]
minus = [120,350,200,320]
hidden = [[0]*len(string) for i in range(len(string))]
for i in range(len(string)-2,-1,-1):
for j in range(i+1,len(string),1):
if string[i] == string[j]:
hidden[i][j] = hidden[i+1][j-1]
else:
hidden[i][j] = min(hidden[i+1][j]+min(add[int(string[i])-1],minus[int(string[i])-1]),hidden[i][j-1]+min(add[int(string[j])-1],minus[int(string[j])-1]))

return hidden[0][len(string)-1]

def back_txt(string):
ahead = string[:int(length/2)-1]
behide = string[int(length/2)+1:]
behide = behide[::-1]
if ahead == behide:
return back_txt(ahead)
else:
return string
ahead = back_txt(string)
num_chaged = string.count(ahead)
cost = gen_back_txt(ahead)
cost = cost * num_chaged
print(cost)

发表于 2022-11-01 23:31:17 回复(0)

可爱抱抱呀😥

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]) throws IOException{
        Read sc=new Read();
        int del[]={-1,120,350,200,320};
        int plus[]={-1,100,200,360,220};
        //int n=sc.nextInt();
        String s=sc.next();
        int n=s.length();
        int ans[][]=new int[n][n];
        for(int d=1;d<n;d++){
            for(int i=0;i<n-d;i++){
                if(s.charAt(i)==s.charAt(i+d)){
                    ans[i][i+d]=ans[i+1][i+d-1];
                }
                else{
                    //删左边：
                    ans[i][i+d]=ans[i+1][i+d]+del[s.charAt(i)-'0'];
                    //删右边：
                    ans[i][i+d]=Math.min(ans[i][i+d],ans[i][i+d-1]+del[s.charAt(i+d)-'0']);
                    //加在左边：
                    ans[i][i+d]=Math.min(ans[i][i+d],ans[i][i+d-1]+plus[s.charAt(i+d)-'0']);
                    //加在右边：
                    ans[i][i+d]=Math.min(ans[i][i+d],ans[i+1][i+d]+plus[s.charAt(i)-'0']);
                }
            }
        }
        sc.print(ans[0][n-1]);
        sc.bw.flush();
        sc.bw.close();
    }
}
//记住看数字范围，需要开long吗，需要用BigInteger吗，需要手动处理字符串吗，复杂度数量级控制在1e7或者以下了吗
//开数组的数据范围最高不能超过1e7，数据范围再大就要用哈希表离散化了
//基本数据类型不能自定义sort排序，二维数组就可以了，顺序排序的时候是小减大，注意返回值应该是int
class Read{
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;
    public Read(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public char nextChar() throws IOException{
        // 确定下一个@可爱抱抱 只有一个字符的时候再用
        return next().charAt(0);
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
    public byte nextByte() throws IOException{
        return Byte.parseByte(next());
    }
    public short nextShort() throws IOException{
        return Short.parseShort(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
    public void println(int a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(int a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(String a) throws IOException{
        bw.write(a);
        bw.newLine();
        return;
    }
    public void print(String a) throws IOException{
        bw.write(a);
        return;
    }
    public void println(long a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(long a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(double a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
    public void print(double a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void print(BigInteger a) throws IOException{
        bw.write(a.toString());
        return;
    }
    public void print(char a) throws IOException{
        bw.write(String.valueOf(a));
        return;
    }
    public void println(char a) throws IOException{
        bw.write(String.valueOf(a));
        bw.newLine();
        return;
    }
}

发表于 2022-10-05 15:38:17 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Character, int[]> map = new HashMap<>();
        map.put('1', new int[]{100, 120});
        map.put('2', new int[]{200, 350});
        map.put('3', new int[]{360, 200});
        map.put('4', new int[]{220, 320});
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            int n = s.length();
            int[][] dp = new int[n][n]; // 变成回文的最小代价
            for (int i = n-1; i >= 0; i--) {
                for (int j = i+1; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i+1][j-1];
                    } else {
                        dp[i][j] = Math.min(dp[i+1][j] + Math.min(map.get(s.charAt(i))[1], map.get(s.charAt(i))[0]),
                                            dp[i][j-1] + Math.min(map.get(s.charAt(j))[0], map.get(s.charAt(j))[1]));
                    }
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }

}

发表于 2022-06-13 19:28:26 回复(0)

缓缓龟

类似找两个字符串的最长相同子序列

#include<iostream>
#include<vector>
#include<string>

using namespace std;
int A[4]={100,200,360,220};
int D[4]={120,350,200,320};

int get_res(int l,int r,string& s,vector<vector<int>>& dp){
    if(l>=r)
        return 0;
    if(dp[l][r])
        return dp[l][r];
    int res=10000000;
    if(s[l]==s[r]){
        res=get_res(l+1,r-1,s,dp);
    }else{
        int S_1=get_res(l+1,r,s,dp)+D[s[l]-'1'];
        int S_2=get_res(l,r-1,s,dp)+D[s[r]-'1'];
        int S_3=get_res(l+1,r-1,s,dp)+D[s[l]-'1']+D[s[r]-'1'];
        int A_1=get_res(l,r-1,s,dp)+A[s[r]-'1'];
        int A_2=get_res(l+1,r,s,dp)+A[s[l]-'1'];
        int A_3=get_res(l+1,r-1,s,dp)+A[s[l]-'1']+A[s[r]-'1'];
        res=min(S_1,min(S_2,min(S_3,min(A_1,min(A_2,A_3)))));
    }
    dp[l][r]=res;
    //cout<<l<<" "<<r<<" "<<res<<endl;
    return res;
}

int main(int argc,char* argv[]){
    string s;
    cin>>s;
    int size=s.size();
    vector<vector<int>> dp(size,vector<int>(size));
    cout<<get_res(0,size-1,s,dp);
    return 0;
}

发表于 2022-03-07 15:41:49 回复(0)

牛客257319613号

s = input()
add_rv = {"1":100, "2":200, "3":200, "4":220}
dp = [[-1 for _ in range(len(s))] for _ in range(len(s))]
res = 0
def is_huiwen(left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
def get_result(left, right):
    if left == right:
        return 0
    if is_huiwen(left, right):
        return 0
    if dp[left][right] != -1:
        return dp[left][right]
    if s[left]==s[right]:
        dp[left][right]=get_result(left+1, right-1)
    else:
        l1 = get_result(left, right-1)+add_rv[s[right]]
        l2 = get_result(left+1, right)+add_rv[s[left]]
        dp[left][right] = min(l1, l2)
    return dp[left][right]
print(get_result(0, len(s)-1))

维护一个最小代价数据即可，递归。

编辑于 2021-10-19 21:43:28 回复(0)

何徐

很经典的字符串+回文的dp，简单来说就是记dp[i][j]为第i个到第j个字符串弄成回文串，最少代价是多少

显然如果str[i]==str[j]，有dp[i][j] = dp[i+1][j-1];

若不相等就是dp[i][j] = min(dp[i+1][j]+dictred[str[i]],dp[i+1][j]+dictadd[str[i]],dp[i][j-1]+dictred[str[j]],dp[i][j-1]+dictadd[str[j]])(dictred和add为代价字典)

最后一个难点就是边界问题，i==j时，dp[i][j] = 0,i != j,则dp[i][j] 只与左边和下边的值有关，所以dp有两种遍历方式，一是i从下往上,一是斜着遍历，讨论版中基本都是从下往上的版本，我写了一个斜着遍历的版本

while True:
    try:
        n = input()
    except:
        break
dictadd = {'1':100,'2':200,'3':360,'4':220}
dictred = {'1':120,'2':350,'3':200,'4':320}
nstr = str(n)
m = len(nstr)
dp = [[0 for _ in range(m)]for _ in range(m)]
for k in range(1,m):
    j = k
    for i in range(m-k):
        if nstr[i] == nstr[j]:
            dp[i][j] = dp[i+1][j-1]
        else:
            dp1 = min(dp[i+1][j]+dictred[nstr[i]],dp[i+1][j]+dictadd[nstr[i]])
            dp2 = min(dp[i][j-1]+dictred[nstr[j]],dp[i][j-1]+dictadd[nstr[j]])
            dp[i][j] = min(dp1,dp2)
        j += 1
print(dp[0][m-1])

发表于 2021-09-24 22:03:23 回复(0)

Python

牛客120963370号

def get_hui(num):
    a = [0,100,200,360,220]
    b = [0,120,350,200,320]
    n = len(num)
    dp = [[0]*n for i in range(n)]
    dp[0][0]=0  for m in range(2,n+1): for i in range(0,n):
            j = i+m-1  if j>=n: break  if num[i]==num[j]:
                dp[i][j]=dp[i+1][j-1] else:
                dp[i][j]=min(dp[i+1][j]+min(a[int(num[i])],b[int(num[i])]),dp[i][j-1]+min(a[int(num[j])],b[int(num[j])])) return dp[0][n-1]
num='12322' print(get_hui(num))

发表于 2021-08-29 14:27:57 回复(0)

寒冰-侠客

字符串转换为题多为动态规划问题，比如两字符串公共子序列，最长回文子序列，字符串最小回文划分。

本题目显然长度为1的子串处理代价0，依次可以推导长度为2,3.。。n的子串。所以属于区间动态规划。

#include <bits/stdc++.h>
using namespace std;
int dp[105][105],add[5]={0,100,200,360,220},del[5]={0,120,350,200,320};
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,n,l,r;
    string s;
    cin>>s;
    n=s.size();
    memset(dp,127/3,sizeof dp);
    for(i=0; i<n; i++) /**< 长度为1肯定代价0 */
        dp[i][i]=0;
    for(i=2; i<=n; i++) /**< 区间动态规划 */
    {
        for(j=0; j<=n-i; j++)
        {
            int k=j+i-1;
            if(s[j]==s[k])
            {
                if(i==2) /**< 长度为2特判，因为不能使用下面dp[j+1][k-1]*/
                    dp[j][k]=0;
                else
                  dp[j][k]=dp[j+1][k-1];
            }
            dp[j][k]=min(dp[j][k],dp[j][k-1]+min(add[s[k]-'0'],del[s[k]-'0']));
            dp[j][k]=min(dp[j][k],dp[j+1][k]+min(add[s[j]-'0'],del[s[j]-'0']));
        }
    }
    cout<<dp[0][n-1];
    return 0;
}

发表于 2021-06-29 22:30:47 回复(0)

LifeAndDonuts

清晰明了的记忆化搜索。

#include <bits/stdc++.h>
using namespace std;
string s;
int n;
vector<vector<int>> memo;
vector<int> add, del;

int dfs(int L, int R) {
    if (R - L <= 0) {
        return 0;
    }
    if (memo[L][R] == -1) {
        if (s[L] == s[R]) {
            memo[L][R] = dfs(L + 1, R - 1);
        } else {
            memo[L][R] = min({
                add[s[R] - '1'] + dfs(L, R - 1), 
                add[s[L] - '1'] + dfs(L + 1, R), 
                del[s[R] - '1'] + dfs(L, R - 1),
                del[s[L] - '1'] + dfs(L + 1, R)
            });
        }
    }
    return memo[L][R];
}
/*
增加一个1，代价：100；删除一个1，代价：120。

增加一个2，代价：200；删除一个2，代价：350。

增加一个3，代价：360；删除一个3，代价：200。

增加一个4，代价：220；删除一个4，代价：320。
*/
int main() {
    cin >> s;
    n = s.size();
    memo.resize(n, vector<int>(n, -1));
    add.resize(4), del.resize(4);
    add[0] = 100, del[0] = 120;
    add[1] = 200, del[1] = 350;
    add[2] = 360, del[2] = 200;
    add[3] = 220, del[3] = 320;
    cout << dfs(0, n - 1) << '\n';
    return 0;
}

发表于 2021-05-17 12:24:37 回复(0)