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

缺乏、安全感 2024-04-17 15:25 19阅读 0赞

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

输入第一行包含三个正整数n,Total,Cost,(a<=n<=5*10*4,1<=Total<=3\*105,103<=Cost<=104)  
接下来两行，每行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);
    
        }
    }