华为

1.:输入一个字符串，对其进行逐词的反转后，然后返回
输入："the sky is blue"
输出："blue is sky the"
注意： 1）“词”是指：任何不含空格的连续字符串
　　　 2）输入字符串可以有首尾空格，但是返回的字符串不能有首尾空格
　　　 3）输入字符串中两个词之间可以有多个空格，但是返回的字符串中词只能用单个空格隔开

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String ss=sc.nextLine();char[] ch=ss.toCharArray();
        int n=ch.length;
        Stack stack=new Stack();
        if(n==0){
            return;
        }
        /*去首尾空格*/
        int i=0;
        /*这里要加上判断条件i<n，否则如果输入的全是空格的话数组会越界*/
        while(i<n&&Character.isWhitespace(ch[i])){
            i++;
        }
        int j=n-1;
        while(j>-1&&Character.isWhitespace(ch[j])){
            j--;
        }
        
        while(j>=i){
            /*如果判断到原字符串的第一个单词，此时将栈中字母弹出即可，不需要输出空格*/
            if(j==i){
                /*这里要记得把第一个字符压入栈*/
                stack.push(ch[j]);
                int size=stack.size();
                for(int k=0; k<size; k++){
                    System.out.print(stack.pop());
                }
            }else if(Character.isSpace(ch[j])){
                /*如果是空格，并且栈不是空，则弹出栈中所有字母，并输出一个空格。
                  这里的栈是否为空判断是为了避免输出可能的多余空格*/
                if(stack.size()!=0){
                    int size=stack.size();
                    for(int k=0; k<size; k++){
                        System.out.print(stack.pop());
                    }
                    System.out.print(" ");
                }
            }else{
                /*是字母的话直接入栈即可*/
                stack.push(ch[j]);
            }
            j--;
        }
    }
}

2.3. LISP语言唯一的语法就是括号要配对。形如 (OP P1 P2 ...)，括号内元素由单个空格分割。其中第一个元素OP为操作符，后续元素均为其参数，参数个数取决于操作符类型

注意：参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 ...)，当前OP类型为 quote / reverse / search / combine 字符串相关的操作：

  • quote: 引用一个字符串，即返回字符串本身内容，参数个数 1

  • reverse: 把字符串反转，并返回，参数个数 1

  • search: 在第一个字符串中查找第二个字符串的第一次出现，返回从这开始到结束的所有字符串，如果查找不到，返回空字符串，参数个数 2

  • combine: 把所有字符串组合起来，参数个数不定，但至少 1 个

其中P1, P2 等参数可能是带双引号的字符串,如 "abc"，也有可能是另外一个 (OP P1 P2 ...)，上述字符串包括引号；引号中间的所有字符，均为 ASCII 可打印字符，且不会再出现引号 (")，输出也为带双引号的字符串

举例:
输入字符串 输出结果
(quote "!@#%") "!@#%"
(reverse "a b c") "c b a"
(search "abcdef" "cd" ) "cdef"
(search "abcdef" "xy" ) ""
(combine "a" "b" "cde) ") "abcde) "
(search (combine "1234567890" "abcdefgh" "1234567890") (reverse "dc")) cdefgh1234567890

输入描述:
合法C字符串，字符串长度不超过512；用例保证了无语法错误.

输出描述:
合法C字符串，需要带括号

输入例子:
(search "huawei" "we")

输出例子:
"wei"

思路：利用栈结构，遇到 "(" 、操作符、操作数都压入栈，遇到")" 持续出栈 直至弹出一个 "("， 计算结果，再将这个结果压入栈。

类似的C++
[编程|300分] 仿LISP字符串运算
题目描述
LISP语言唯一的语法就是括号要配对。
形如 (OP P1 P2 …)，括号内元素由单个空格分割。
其中第一个元素OP为操作符，后续元素均为其参数，参数个数取决于操作符类型
注意：参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 …)
当前OP类型为add/sub/mul/div(全小写)，分别代表整数的加减乘除法。简单起见，所以OP参数个数为2
举例
-输入：(mul 3 -7)输出：-21
输入：(add 1 2) 输出：3
输入：(sub (mul 2 4) (div 9 3)) 输出 ：5
输入：(div 1 0) 输出：error
常规方法是用两个栈分别存放操作数和操作符，本文用一个栈来实现，首先从后往前提取操作数和操作符存放在vector，然后判断。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String ss=sc.nextLine();
        Stack<String> stack=new Stack<String>();
        StringBuilder temp1=new StringBuilder();  //字符串缓存，用来判断累积读入的字符是否构成一个操作数/操作符
        List<String> temp2=new ArrayList<String>(); //用于存储栈弹出来的操作数
        char[] chars=ss.toCharArray();
        int n=chars.length;
        /*从左往右扫描字符数组*/
        for(int i=0;i<n;i++){
            /*如果是 ( ，要判断是否实在操作数中，是的话加入缓存字符串，不是的话直接入栈*/
            if(chars[i]=='('){
                if(temp1.indexOf("\"")==-1){
                    stack.push("(");
                }else{
                    temp1.append('(');
                }
            }
            /*如果是 ) ，要判断是否实在操作数中，是的话加入缓存字符串，不是的话出栈至遇到一个 ( */
            else if(chars[i]==')'){
                /*根据缓存字符串中有没有 " 来判断是否在一个操作数中*/
                if(temp1.indexOf("\"")!=-1){
                    temp1.append(')');
                }else{
                    String back=stack.pop();
                    while(!back.equals("(")){
                        temp2.add(back);
                        back=stack.pop();
                    }
                    String operator=temp2.get(temp2.size()-1);
                    switch(operator){
                        case "quote":
                            stack.push("\""+(temp2.get(0)).replaceAll("\"","")+"\"");
                        break;
                        case "search":
                            stack.push(search(temp2.get(1),temp2.get(0)));
                        break;
                        case "reverse":
                            stack.push(reverse(temp2.get(0)));
                        break;
                        case "combine":
                            String stringComb=combine(temp2.subList(0,temp2.size()-1));
                            stack.push(stringComb);
                        break;
                    }
                    temp2.clear();
                }
            }
            /*如果是空格，判断空格是否在操作数字符串中，不是的话原先的字符串缓存已经构成一个操作数/符，压入栈。
              是的话加入到字符串缓存中*/
            else if(chars[i]==' '){
                if(temp1.indexOf("\"")!=-1){
                    temp1.append(chars[i]);                
                }else{
                    if(temp1.length()>0){
                        String tempString=temp1.toString();
                        stack.push(tempString);
                        temp1.setLength(0);
                    }
                }
            }
            /*如果遇到成对的 " ，表明缓存的是一个操作符/数，将其压入栈*/
            else if((chars[i]=='\"')&&(temp1.indexOf("\"")!=-1)){
                if(temp1.length()>0){
                        temp1.append('\"');
                        String tempString=temp1.toString();
                        stack.push(tempString);
                        temp1.setLength(0);
                    }
            }
            /*字母或者数字的情况直接加入到字符串缓存*/
            else{
                temp1.append(chars[i]);
            }
        }
        for(int i=0;i<stack.size();i++){
            System.out.print(stack.pop());
        }
    }
    
    static String search(String s1,String s2){
        s1=s1.replaceAll("\"","");
        s2=s2.replaceAll("\"","");
        if(s1.indexOf(s2)!=-1){
            return "\""+s1.substring(s1.indexOf(s2))+"\"";
        }else{
            return  "\""+ "\"";
        }
    }
    
    static String reverse(String s){
        s=s.replaceAll("\"","");
        StringBuilder sb=new StringBuilder();
        char[] chars=s.toCharArray();
        for(int i=chars.length-1;i>=0;i--){
            sb.append(chars[i]);
        }
        return "\""+sb.toString()+"\"";
    }
    
    static String combine(List<String> l){
        StringBuilder sb=new StringBuilder();
        for(int i=l.size()-1;i>=0;i--){
            String s=(l.get(i)).replaceAll("\"","");
            sb.append(s);
        }
        return "\""+sb.toString()+"\"";
    }
}

注：

判断StringBuilder是否为空：temp1.length()>0，通过长度是否大于0来判断，以及利用setLength(0)来清空StringBuilder中的内容

import java.util.Stack;
 
public class problem {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        String string = "(div 2 (sub 5 (add 3 2)))";//这里改成标准输入
        
        StringBuffer inputString = new StringBuffer(string);
        
        Stack<Integer> numberBuffer = new Stack<Integer>();
        Stack<String> operationBuffer = new Stack<String>();
        int mark = 0;
        int ParameterOne = 0;
        int ParameterTwe = 0;
        
        for(int index = 0;index<inputString.length();index++) {
            if('(' == inputString.charAt(index)) {
                operationBuffer.push(inputString.substring(index+1, index+4));
                index+=4;
                mark = index+1;
            }else if (')' == inputString.charAt(index)) {
                if(mark<index) {
                    numberBuffer.push(Integer.parseInt(inputString.substring(mark, index)));
                    index++;
                    mark = index+1;
                }
                ParameterTwe = numberBuffer.pop();
                ParameterOne = numberBuffer.pop();
                
                switch(operationBuffer.pop()) {
                case "add":
                    numberBuffer.push(ParameterOne + ParameterTwe);
                    break;
                case "sub":
                    numberBuffer.push(ParameterOne - ParameterTwe);
                    break;
                case "mul":
                    numberBuffer.push(ParameterOne * ParameterTwe);
                    break;
                case "div":
                    if(ParameterTwe == 0) { 
                        System.out.println("error");//这里是error输出
                        return;
                        }
                    else{
                        numberBuffer.push(ParameterOne / ParameterTwe);
                        }
                    break;
                }
                
            }else {
                if(' ' == inputString.charAt(index)) {
                    if(mark<index) {
                numberBuffer.push(Integer.parseInt(inputString.substring(mark, index)));
                //index++;
                mark = index+1;
                }
                }
            }
        }
        
        while(!operationBuffer.isEmpty()) {
            ParameterTwe = numberBuffer.pop();
            ParameterOne = numberBuffer.pop();
            
            switch(operationBuffer.pop()) {
            case "add":
                numberBuffer.push(ParameterOne + ParameterTwe);
                break;
            case "sub":
                numberBuffer.push(ParameterOne - ParameterTwe);
                break;
            case "mul":
                numberBuffer.push(ParameterOne * ParameterTwe);
                break;
            case "div":
                if(ParameterTwe == 0) { 
                    System.out.println("error");
                    }
                else{
                    numberBuffer.push(ParameterOne / ParameterTwe);
                    }
                break;
            }
            
        }
        
        System.out.println(numberBuffer.pop().toString());//这里改成标准输出
        return;
    }
 
}

面试题一:获取最长对称串的长度
题目描述：

输入一个字符串，输出该字符串中对称的子字符串的最大长度，比如输入字符串“12213”，由于该
字符串里最长的对称子字符串是“1221”，因此输出为4.
输入描述：
连续的字符串，字符串长度不超过64，只包含数字和字母
输出描述：
最长的对称字符串长度
示例1：
输入
12321abc
输出

5

import java.util.Scanner;
 
public class Main {
    /**
     * 华为2019春招面试编程题：获取最长的对称字符串长度
     * @param str
     * @return
     */
    public static int GetlongestSymStr(String str){  
        int n=str.length();  
        boolean[][] dp=new boolean[n][n];  
        int maxLen=0;  
        for(int i=0;i<n;i++){  
            for(int j=i;j>=0;j--){   
                if(str.charAt(i)==str.charAt(j) && (i-j<2 || dp[j+1][i-1]==true)){  
                    dp[j][i]=true;  
                    maxLen=Math.max(maxLen, i-j+1);  
                }  
            }  
        }  
        return maxLen;  
    } 
    public static void main(String[] args){ 
        Scanner sc = new Scanner(System.in);    
        String s = sc.nextLine();  
        System.out.println(GetlongestSymStr(s));  
    }
}

面试题二：IPV6地址分类

题目描述：

ipv6地址为128位，完整的文本格式写成8段16位的形式，例如：
2001:1002：FFFF:ABCD:1234:1234:0000:0001
简写时，会将其中全0的字段压缩，例如：
2001:0000:0000:0000:0000:0000:0000:0001会简写成2001::0001
0000:0000:0000:0000:0000:0000:0000:0001会简写成::0001或者::1
ipv6地址包括以下类型：
地址类型 地址前缀(二进制) ipv6前缀标识
单播地址 未指定地址 00....0(128 bits) ::/128
环回地址 00...1(128 bits) ::1/128
链路地址 1111111010 FE80::/10
站点本地地址 1111111011 FEC0::/10
全球单播地址 其他形式
组播地址 11111111 FF00::/8

任播地址 从单播地址空间进行分配，使用单播地址的格式

备注：地址标识中一般以“/"后带的数字来表示掩码，例如上面的"FF00::/8"表示的是前8比特为1，后面120比特为任意值。请实现一段代码，来判断输入的IPV6地址字符串的类型
输入描述：
一行字符串，完整形式的IPV6地址
输出描述：
输出一个字符串，表示是何种类型的IPV6地址，输出可以是：
Unspecified 未指定地址
Loopback 环回地址
LinkLocal 链路本地地址
SiteLocal 站点本地地址
GlobalUnicast 全球单播地址
Multicast 组播地址
Error 错误的地址，或者非完整形式IPV6地址的字符串
示例1：
输入：
FE81:0001:0000:0000:FF01:0203:0405:0607
输出:
LinkLocal

（代码带更新）
面试题目三：应用下载顺序

题目描述：

华为应用市场举办安装应用奖励金币活动，不同的应用下载、试玩需要的流量大小不同，奖励的金币数量也不同，同一个应用多次下载只奖励一次金币，小花月末有一定的余量，计算下载哪些应用可以获取的金币最多？相同金币情况下，优先排名靠前的应用
输入描述：
输入分三行
第一行：流量数，单位MB,整数
第二行：应用排名顺序，下载、试玩需要流量数，单位MB,整数
第三行：应用奖励的金币数
输出描述：
输出应用列表：建议下载的应用顺序号，用一个空格分隔
示例1：
输入
40
12 13 23 36
11 11 20 30
输出：
1 3
说明：

注意输出：开头、末尾没有空格

思路分析：

本题实际是一个01背包模型，具体分析参考我的另一篇有关背包问题的文章。

import java.util.Scanner;
 
public class Main{
    /**
     * 华为2019春招面试编程题：应用下载顺序
     * @param numOfLL 剩余流量数
     * @param needLL 下载应用排名及消耗流量数
     * @param reword 下载奖励金币数
     * @return
     */
    public static String SequenceOfDownload(int numOfLL,int[] needLL,int[] reword){
        
        return ZeroOnePack(numOfLL,needLL.length,needLL,reword);
    }
    /**
     * @param V 背包容量
     * @param N 物品种类
     * @param weight 物品重量
     * @param value 物品价值
     * @return
     */
    public static String ZeroOnePack(int V,int N,int[] weight,int[] value){
        
        //初始化动态规划数组
        int[][] dp = new int[N+1][V+1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                //如果第i件物品的重量大于背包容量j,则不装入背包
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if(weight[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        int maxValue = dp[N][V];
        //逆推找出装入背包的所有商品的编号
        int j=V;
        String numStr="";
        for(int i=N;i>0;i--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            if(dp[i][j]>dp[i-1][j]){
                numStr = i+" "+numStr;
                j=j-weight[i-1];
            }
            if(j==0)
                break;
        }
        return numStr;  
    }
    public static void main(String[] args){ 
        Scanner sc = new Scanner(System.in);  
        int numOfLL = Integer.parseInt(sc.nextLine());
        String str2 = sc.nextLine();
        String str3 = sc.nextLine();
        String[] needLL;
        String[] reword;
        needLL= str2.split(" ");
        reword = str3.split(" ");
        
        int[] Reword = new int[needLL.length];
        int[] NeedLL = new int[reword.length];
        for(int i=0;i<needLL.length;i++){
            NeedLL[i] = Integer.parseInt(needLL[i]);
            Reword[i] = Integer.parseInt(reword[i]);
        }
        String result = SequenceOfDownload(numOfLL,NeedLL,Reword);
        result = result.substring(0,result.length()-1);
        System.out.println(result); 
        sc.close();  
    }
}

今年华为优招笔试总共三道编程题

一 、歌唱打分

青年歌手大赛评委打分，打分规则是去掉一个最高分和一个最低分，然后计算平均分。

输入描述：输入数据有多组，每组占一行，每行第一个数n表示评委人数，然后是n个评委的打分

输出描述：输出保留两位小数，每组输出一行

示例：

输入：

3 99 98 97

4 100 99 98 97

输出：

98.00

98.50

二、猜数字

xAyB猜字游戏，输入两组数字，每组数字包含4个非负整数，同一组中的四个数字互不相同，数字间以空格分隔。

第一组数字为猜数字游戏的正确答案，第二组数字为玩家所猜的答案，根据以下规则输出猜数字的结果xAyB。

规则1：如果数字相同，且位置相同，则得到一个A

规则2：如果数字相同，且位置不同，则得到一个B

输入描述：两组数字，每组数字包含4个非负整型数字，同一组中的四个数字互不相等，数字以空格分隔

输出描述：xAyB

示例：

输入：

1 2 3 4

1 2 5 3

输出：

2A1B

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        String[] array1 = s1.split(" ");
        String[] array2 = s2.split(" ");
        int stateA = 0;
        int stateB = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array2.length; j++) {
                if (array1[i].equals(array2[j])) {
                    if (i == j) {
                        stateA++;
                    } else {
                        stateB++;
                    }
                }
            }
        }
        System.out.printf("%dA%dB",stateA,stateB);
    }
}

三、独木桥

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入描述：输入文件river.in的第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出描述：输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。

示例：

输入：

10

2 3 5

2 3 5 6 7

输出：

2

参考这位大神的帖子：https://blog.csdn.net/zero_from/article/details/52958796

第一题：

找出输入字符串中的重复字符，在根据ASCII把重复的字符从小到大排列（字符串长度不超过100）

示例：输入：ABCABCdd 输出： ABCd

代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main()
{
    string str;
    cin>>str;
    int len=str.size();
    vector<int> v(126);
    for(int i=0;i<len;i++)
    {
           v[(int)(str[i])]++;
    }
    for(int j=0;j<126;j++)
    {
        if(v[j]>1)
            cout<<(char)j;
    }
    cout<<endl;
    return 0;
}

第二题：

给定一串字符，里面有些字符有连续出现的特点，请寻找这些连续出现字符中最长的串。如果最长的串有多个，请输入字符ASCII码最小的那一串

示例：aaabbbccccccccccccczzzz 输出：ccccccccccccc

代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()
{
    vector<int> vec(256, 0);
    vector<int> vec1(256, 0);
    string charm;
    while (cin >> charm)
    {
        if (charm.size() == 0)
            return 0;
        if (charm.size() == 1)
        {
            cout << charm[0];
            return 0;
        }
    /*  for (int i = 0;i<charm.size();i++)
        {
            vec[charm[i]] = vec[charm[i]] + 1;
        }*/
        int count = 0;
        int flag = 0;
        for (int i = 0;i<charm.size()-1;i++)
        {
            count++;
            if (charm[i] != charm[i + 1]|| flag)
            {
                if(vec[charm[i]]<count)
                    vec[charm[i]] = count;
                count = 0;
            }
        }
        if (charm[charm.size() - 2] == charm[charm.size() - 1])
        {
            count++;
            if (vec[charm[charm.size() - 2]] < count)
            {
                vec[charm[charm.size() - 2]] = count;
                count = 0;
            }
        }
        if (charm[charm.size() - 2] != charm[charm.size() - 1])
        {
            if (vec[charm[charm.size() - 1]] < 1)
            {
                vec[charm[charm.size() - 1]] = 1;
            }
        }
 
        auto max = max_element(vec.begin(), vec.end());
        int index = 0;
        for (int i = 0;i<256;i++)
        {
            if (*max == vec[i])
            {
                index = i;
                break;
            }
        }
        for (int i = 0;i<*max;i++)
        {
            cout << (char)index;
        }
        for (int i = 0;i<256;i++)
        {
            vec[i] = 0;
        }
        cout << endl;
        int i = 0;
    }
}
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main()
{
    vector<int> vec(126,0);
    string s1;
    cin>>s1;
    int len=s1.size();
    int max=0;
    int index=0;
    for(int i=0;i<len;i++)
    {
        vec[int(s1[i])]++;
    }
    for(int i=0;i<126;i++)
    {
        if (vec[i]>max)
        {
            max=vec[i];
            index=i;
        }
    }
    for(int i=max;i>0;i--)
    {
        cout<<(char)index;
    }
}

8.15：

知道问题所在了，加入字符串是aaabbbbbbbbbbbbbaaaccccccccaaaaaaaa；

代码中把a叠加起来了，这是不对的

第三题：属于邮局问题（动态规划）

已知某小镇的房子沿直线分布，给定一个有序整型数组arr，里面的每个值代表小镇每栋房子的一维坐标点。

现在需要建N个广告牌，广告牌只能建在这些坐标点上，使得每个坐标点离广告牌的总距离最短，请返回这个最短的总距离。

#include <iostream>
 
#include <string.h>
 
#include <stdio.h>
 
#include <vector>
 
 
 
using namespace std;
 
const int INF = ~0U >> 1;
 
const int N = 305;
 
 
 
int w[N][N];
 
int dp[N][35];
 
int a[N];
 
int n, m;
 
 
 
void Init(int a[], int n)
 
{
 
    memset(w, 0, sizeof(w));
 
    for (int i = 1; i <= n; i++)
 
    for (int j = i + 1; j <= n; j++)
 
        w[i][j] = w[i][j - 1] + a[j] - a[(i + j) >> 1];
 
}
 
 
 
int Work()
 
{
 
    for (int i = 1; i <= n; i++)
 
    {
 
        dp[i][i] = 0;
 
        dp[i][1] = w[1][i];
 
    }
 
    for (int j = 2; j <= m; j++)
 
    {
 
        for (int i = j + 1; i <= n; i++)
 
        {
 
            dp[i][j] = INF;
 
            for (int k = j - 1; k<i; k++)
 
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + w[k + 1][i]);
 
        }
 
    }
 
    return dp[n][m];
 
}
 
 
 
int main()
 
{
 
    vector<int> arr;
    int x;
    
    while (cin >> x)
    {
        arr.push_back(x);
    }
    int len = arr.size();
     m = arr[len - 1];
     n = len - 1;
        for (int i = 1; i <= n; i++)
 
            a[i]=arr[i-1];
 
        Init(a, n);
 
        printf("%d\n", Work());
 
    
 
 
 
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,723评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,003评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,512评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,825评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,874评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,841评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,812评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,582评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,033评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,158评论 5赞 341
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,789评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2赞 352

推荐阅读更多精彩内容