从A序列中选择一个非空前缀，再从B序列中选择一个非空前缀，要求选择的这两个前缀的末尾元素相等。把这两个前缀移除，这个操作将花费Cost代价，但是这个操作可以使你得到一颗宝石。

56 阅读 0 评论 37 点赞

我是靠谱客的博主阳光芹菜，最近开发中收集的这篇文章主要介绍从A序列中选择一个非空前缀，再从B序列中选择一个非空前缀，要求选择的这两个前缀的末尾元素相等。把这两个前缀移除，这个操作将花费Cost代价，但是这个操作可以使你得到一颗宝石。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

滴滴笔试题：
现在有A,B两个序列，两个序列都是拥有n个元素，你有两种操作：
1.从A序列中选择一个非空前缀，再从B序列中选择一个非空前缀，要求选择的这两个前缀的末尾元素相等。把这两个前缀移除，这个操作将花费Cost代价，但是这个操作可以使你得到一颗宝石。
2.您可以重复第一步的操作；最终，您需要花费两个序列剩余元素数量之和大小的代价，移除两个序列中剩下的所以元素（这最后一步是没有宝石的），这时游戏结束。
要求总代价不超过Total,且序列中不得有剩余，那么最多可以获得多少宝石。

输入第一行包含三个正整数n,Total,Cost,(a<=n<=5104,1<=Total<=3*10⁵,10³<=Cost<=10⁴)
接下来两行，每行n个数，表示A,B序列

输出：一个数表示最多可以获得的宝石数量

样例输入:
5 10000 1000
1 5 4 2 3
5 4 3 2 1
样例输出
3
提示
按顺序消除末尾为5，4，3的前缀，最后消除2，1，可以获得3颗宝石

简单来说题意：
就是给你两串序列A,B，在第一个序列里面找一个前缀，再从第二个序列里面找一个前缀，要求这两个前缀必须末尾元素相等。找到之后就把这两个前缀从所在的序列中删除，就会给你一颗宝石，接下来继续找，继续删。

我的思路：（不是最好，勿喷）
遍历两个序列，找到相同的元素，把这两个元素的索引相加存起来（再将此时的两个索引也存起来），依次找到所有相同的元素的索引之和，排序后，找到最小的，然后找出此索引和对应的两个序列元素的索引，然后切掉其前缀，再在剩下的序列中重复上述步骤。

代码：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] split = s.split(" ");
        int n = Integer.parseInt(split[0]);
        int Total = Integer.parseInt(split[1]);
        int Cost = Integer.parseInt(split[2]);
        int result = 0;
        int myCost=0;
        if (!(Total >= 1 && Total <= 3 * 10 * 10 * 10 * 10 * 10)) {
            System.out.println("error");
            return;
        }
        if (!(Cost >= 10*10*10 && Cost <=  10 * 10 * 10 * 10)) {
            System.out.println("error");
            return;
        }
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        if (s1.length()!=5||s2.length()!=5){
            System.out.println("error");
            return;
        }
        String[] split1 = s1.split(" ");
        String[] split2 = s2.split(" ");
        //方便后面根据索引截取，所以去掉空格
        String replace1 = s1.replace(" ", "");
        String replace2 = s2.replace(" ", "");
        System.out.println("replace1: " + replace1);
        System.out.println("replace2: " + replace2);
        while (replace1.length() != 0 && replace2.length() != 0) {
            ArrayList<Integer> listSum = new ArrayList<>();
            ArrayList<Integer> listIndex = new ArrayList<>();
            for (int i = 0; i < split1.length; i++) {
                for (int i1 = 0; i1 < split2.length; i1++) {
                    if (split1[i].equals(split2[i1])) {
                        listSum.add(i + i1);
                        listIndex.add(i);
                        listIndex.add(i1);
                    }
                }
            }
            if (listSum.size() == 0) {
                //证明序列A，B没有相同的元素
                break;
            }
            //找到最短的且末尾元素相同的前缀的索引
            listSum.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            int index1 = 0;
            int index2 = 0;
            for (int i = 0; i < listIndex.size(); i += 2) {
                if (listIndex.get(i) + listIndex.get(i + 1) == listSum.get(0)) {
                    index1 = listIndex.get(i);
                    index2 = listIndex.get(i + 1);
                    //满足上述条件，证明序列AB可以截取，所以宝石加一
                    result++;
                    myCost+=Cost;
                    break;
                }
            }
            replace1 = replace1.substring(index1 + 1);
            replace2 = replace2.substring(index2 + 1);
            split1 = replace1.split("");
            split2 = replace2.split("");
            System.out.println("replace1: " + replace1);
            System.out.println("replace2: " + replace2);

        }
        int i = replace1.length() + replace2.length();
        if (myCost+i*Cost>Total){
            System.out.println("花费超出");
        }else System.out.println(result);

    }
}