动态规划题目总结

男娘i 2022-09-25 01:14 199阅读 0赞

题目1：

##### 输出描述: #####

对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。

##### 输入例子: #####

2
    7
    89 256 78 1 46 78 8
    5
    6 4 8 2 17

##### 输出例子: #####

3
    3

package dynamatic;
    
    import java.util.Scanner;
    
    public class D1 {
     
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
            	//1.初始化
                int count = in.nextInt();      
                for (int i=0; i<count; i++) {
                    int length = in.nextInt();
                    int[] array = new int[length];
                    int[] values = new int[length];
                    for (int j=0; j<length; j++) {
                        array[j] = in.nextInt();
                    }
                    findMaxSLength(array, values);
                }
            }
         
        }
         //1.深度优先搜索
        public static void findMaxSLength(int[] array, int[] values) {       
            int length = array.length;
            for (int i=0; i<length; i++) {
                if (i==0) {
                    values[i] = 1;
                } else {
                     
                    int max = 0;
                    for (int j=i-1; j>=0; j--) {
                        if (array[j] < array[i]) {
                        	//2.关键的判断value[]--[1, 1, 2, 1, 3]在此基础上判断，倒推，动态更新
                            int temp = values[j] + 1;
                            if (temp > max) {
                                max = temp;
                            }
                        }
                        values[i] = max == 0?1:max;
                    }                
                }
            }        
            int max=0;
            for (int k : values) {
                if (k>max) {
                    max = k;
                }
            }
            System.out.print(max);    
        }
    }

**变化**

##### 输入例子: #####

2
    7
    89 256 78 1 46 78 8
    5
    6 4 8 2 17

##### 输出例子: #####

1 46 78
    6 8 17

package dynamatic;
    
    import java.util.Scanner;
    import java.util.List;
    import java.util.ArrayList;
     
    public class D22 {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int size = in.nextInt();
                for (int i = 0; i < size; i++) {
                    int len = in.nextInt();
                    int[] data = new int[len];
                    for (int j = 0; j < len; j++) {
                        data[j] = in.nextInt();
                    }
                    lisB(data);
                   
                }
               
            }
            in.close();
        }
     
        public static  void lisB(int[] array) { //dp时间复杂度（o(n2)）
        	//边界判断
            ArrayList<Integer> result = new ArrayList<>();
            if(array == null || array.length == 0) return;
            int length = array.length;
            //存储各个位置
            ArrayList<ArrayList<Integer>> buffer = new ArrayList<>();//每个索引下的最大子序列长度列
            //DFS
            for(int i = 0; i < length; i++) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(array[i]);
                buffer.add(temp);
                for(int j = i - 1; j >= 0; j--) {                
                    if(array[i] > array[j] && buffer.get(i).size() <= buffer.get(j).size()) {  //j < i && array[j] < array[i]
                        buffer.set(i,new ArrayList<Integer>(buffer.get(j)));   //
                        buffer.get(i).add(array[i]);
                    }
                    
                }
                if(result.size() < buffer.get(i).size()) {
                    result = buffer.get(i);
                }
            }
            
            for (int j = 0; j < result.size(); j++) {
            	if (j==result.size()-1) {
            		System.out.print(result.get(j));
    			}else {
    				
    				System.out.print(result.get(j)+" ");
    			}
    		}
           // return result;
        
        }
    }

2.求CD个数

你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？

##### 输入描述: #####

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。 保证 n ≤ 100 , s ≤ L ≤ 10000

##### 输出描述: #####

输出一个整数代表你至少需要的 CD 数量。

##### 输入例子: #####

7 2 6

##### 输出例子: #####

package dynamatic;
    
    import java.util.*;
     
    public class D4CD{
         
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();//歌曲总数
                int s = in.nextInt();//每首哥的时间
                int l = in.nextInt();//CD容量
                int count = (l+1)/(s+1);//每张容纳多少歌曲---都加一个空，看为整体（最大值）
                count = Math.min(n, count);//防止歌曲过少
                if(count%13==0){
                    count--;
                }
                int sum = n/count;//需要多少CD
                int yu = n%count;//余数！！！！最后一个专辑剩下的歌曲
                /*
                 * yu是最后一张专辑的歌曲数，如果yu是13的倍数，为了不增加专辑的数量，---没张容纳》13
                 * 我们可以考虑从倒数第二张专辑中借一首歌，此时倒数第二张专辑的歌曲数是count-1，
                 * 若(count-1)==yu，这种情况只能在多出一张专辑。不知道有没有讲明白？我的表述有点不到位，防止最后count-1为13倍数。
                 * 
                 * */
                if(yu!=0){
                    sum++;
                    if(yu%13==0&&(count-yu)==1){//查看最后最后一张专辑的情况
                        sum++;
                    }
                }
                System.out.println(sum);
            }
        }
    }

3.背包问题

小萌是个WOW发烧友，每天都痴迷于他的法师号。精诚所至金石为开，小萌穿越到WOW的世界中了...  
初来乍到的小萌在暴风城的小巷中，遇见了一位善良的德鲁伊。德鲁伊听了小萌的故事，打算帮助他在WOW这个世界好好活下去，于是，把自己的东西都给了小萌了...  
德鲁伊的东西太多了，于是小萌去拍卖行买了几个包裹，一切妥当之后，小萌开始把东西装进包裹里。  
不过，因为小萌穿越时候脑袋先着地，所以脑子不好用，每次他拿起一个物品，要不装进包里，要不就直接扔掉...  
而且，一个背包一旦不往里装东西，小萌就会封上口不再用...  
现在，告诉你小萌每个物品的体积，背包的个数和容量，以及小萌拿物品的顺序，你要帮助小萌求出他能拿走多少东西。

##### 输入描述: #####

输入的第一行为一个整数T，代表测试数据组数。
    
      第一行：三个正整数 N、T、M。 分别表示物品的个数，背包的容量，背包个数。
    
      第二行：N个数。表示每个物品的体积。
    
      保证：
    
      1<=N,T,M<=20,0<=vi<=30

##### 输出描述: #####

对于每组数据，输出一个整数，代表小萌可以拿走的最多物品个数。

##### 输入例子: #####

2
    5 5 2
    4 3 4 2 1

##### 输出例子: #####

**例4数石子：找规律**

Alice 和 Bob 在玩一个取石子的游戏，有 n 堆石子，第 i 堆有 ai 个石子，两个人轮流行动，Alice 先手。每个人每次行动必须选择一堆非空的石子，拿走其中的一部分石子，谁不能行动谁就输了。

他们玩过很多次这个游戏之后都觉得太无聊了，于是决定给游戏增加一个要求：当某个人要拿第 i 堆中的石子时必须要保证第 1 .. i-1 堆的石子都已经拿光了。也就是说两个人必须先拿光第 1 堆中的石子，然后再拿第 2 堆的，第 3 堆的……以此类推。

所以现在问在这个新游戏规则下，两个人都知道石子的堆数和每堆的数量，假设两个人都绝顶聪明而且不会失误，先手的 Alice 是否一定可以必胜？

##### 输入描述: #####

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n (1 ≤ n ≤ 60) ， 接下来一行有 n 个整数 ai 表示第 i 堆的石子数量( 1 ≤ ai ≤ 1000000000)。

##### 输出描述: #####

如果 Alice 必胜，输出 Alice，否则输出 Bob。
    
     对于样例，Alice 第一步只能拿走第 1 堆上的 1 个石子，接下来 Bob 只要拿走第 2 堆上的全部石子即可获胜。但如果两堆石子数分别是 2 1 ，那么 Alice 就必胜了。

##### 输入例子: #####

2
    1 2

##### 输出例子: #####

Bob

//总结：先分析清楚题目的规律！！！！！----下笔如有神助

package dynamatic;
    
    import java.util.Scanner;
    
    public class D4 {
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		boolean flag = false;// 找规律！！！12大数字前面奇数个1，--bob，偶数个----alice
    		//只输入一次！！
    		while (s.hasNext()) {
    			int n = Integer.parseInt(s.nextLine());
    			int[] a = new int[n];
    			String[] str = s.nextLine().split(" ");
    			int count = 0;
    			int temp = 0;
    			for (int i = 0; i < str.length; i++) {//得到超过1的最早位置
    				if (Integer.parseInt(str[i]) > 1) {
    					temp = i;
    					break;
    				}
    			}
    			for (int j = 0; j < temp; j++) {
    				if (Integer.parseInt(str[j]) == 1) {//统计1的个数
    					count++;
    				}
    			}
    
    			if (count % 2 == 0) {//奇数偶数判断
    				flag = false;
    				break;
    			} else {
    				flag = true;
    				break;
    			}
    
    		}
    
    		if (flag) {
    			System.out.println("Bob");
    		} else {
    			System.out.println("Alice");
    		}
    
    	}
    
    }