最小旅行线路-动规

蔚落 2023-05-22 10:30 9阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]

**Sample Input**  
3  
1 1 2 2 3 3  
**Sample Output**  
9

分析是我们可以发现，每次选择下一个点的时候我都有两个选择（两个相同美丽值的位置），要做的是选择哪一个美丽值的位置，就是要选择最小路线的走法，如果能保证每一步都是最小的走法，那么总的走法也当然是最小的！！！

import java.util.ArrayList;
    import java.util.Scanner;
    
    
    public class Main{
        
        static int dp[][]=new int[200005][2];
        static int map1[][]=new int[200005][2];
    
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            for (int i = 1; i <=2*n ; i++) {
        
                int x=scanner.nextInt();
                if (map1[x][0]==0)map1[x][0]=i;
                else map1[x][1]=i;
            }
            dp[1][1]=map1[1][1]-1;//要先从1位置开始知道美丽值为1处
            dp[1][0]=map1[1][0]-1;
            for (int i = 2; i <=n ; i++) {
        
                if (dp[i-1][1]+Math.abs(map1[i][0]-map1[i-1][1])+dp[i-1][0]+Math.abs(map1[i][1]- map1[i-1][0])<dp[i-1][1]+Math.abs(map1[i][1]-map1[i-1][1])+dp[i-1][0]+Math.abs(map1[i][0]- map1[i-1][0])){
        
                //我这个值走到下一个位置有两个选择，我要选择最小的路
                    dp[i][0]=dp[i-1][1]+Math.abs(map1[i][0]-map1[i-1][1]);
                    dp[i][1]=dp[i-1][0]+Math.abs(map1[i][1]-map1[i-1][0]);
                }else {
        
                    dp[i][1]=dp[i-1][1]+Math.abs(map1[i][1]-map1[i-1][1]);
                    dp[i][0]=dp[i-1][0]+Math.abs(map1[i][0]-map1[i-1][0]);
                }
            }
            System.out.println(dp[n][1]+dp[n][0]);
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230521/41f9629df2c84e81886b8614c147200a.png