第十周

缺乏、安全感 2023-01-20 08:15 74阅读 0赞

### 记录 ###

*  A.最长递增子序列
 *   *  代码
 *  B.构造最长递增子序列
 *   *  代码
 *  C.0-1背包
 *   *  代码
 *  D.X星人的基因
 *   *  代码
 *  E.出列人数
 *   *  代码
 *  F.XP的午餐
 *   *  代码

# A.最长递增子序列 #

**题目描述**

*  给出一个序列a1,a2,a3,a4,a5,a6,a7…an，求它的一个子序列（设为s1,s2,…sn），使得这个子序列满足这样的性质：s1<s2<s3<…<sn并且这个子序列的长度最长。输出这个最长子序列的长度，要求时间复杂度为O(n^2)。

**输入**

*  每组输入包括两行，第一行为序列长度n，第二行为序列。

**输出**

*  输出最长递增子序列的长度。

**样例输入 Copy**

7
    1 7 3 5 9 4 8

**样例输出 Copy**

> 【这个题目老师上课的时候讲过了，但是我真的真的一遇到数组就超限啊，我也没把办法呀，我说怎么代码明明没有问题，平台一直不该给我过，室友一语点通，数组开太小了，好家伙，我把数组改了，就过了，就离谱！生气！生我自己的气！】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int n,maxlen,max;
    	public static int []a = new int[105000];
    	public static int []b = new int[105000];
    // public static int []pre = new int[105];
    	
    	public static void solve(){ 
    		b[1]=1;
    		max = 0;
    		for(int i=2;i<=n;i++){ //分阶段
    			maxlen = 0;
    			for(int j=i-1;j>=1;j--){ 
    				if(a[j]<a[i]&&b[j]>maxlen){ 
    					maxlen = b[j];
    				}
    			}
    		b[i] = maxlen+1;
    				
    		if(b[i]>max)
    			max = b[i];//存储最长递增子序列的长度
    		}
    	}
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=1;i<=n;i++)
    				a[i] = sc.nextInt();
    			solve();
    			System.out.println(max);
    		}
    	}
    }

# B.构造最长递增子序列 #

**题目描述**

*  在“最长递增子序列”的基础上对代码进行改进，输出一条最长递增子序列。

**输入**

*  每组输入包括两行，第一行为序列长度n，第二行为序列。

**输出**

*  输出最长递增子序列中的任意一条即可。

**样例输入 Copy**

7
    1 7 3 4 9 2 3

**样例输出 Copy**

1 3 4 9

> 【这个和第一题老师都讲过啦，只是我的输出有问题，把输出m\[1\]\[c\]改成了m\[0\]\[c\]就好啦！还是放个链接——[戳我！戳我！][Link 1]】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int n,maxlen,lab;
    	public static int []a = new int[105000];
    	public static int []b = new int[105000];
    	public static int []c = new int[105000];
    	public static int []pre = new int[105000];
    	
    	public static void solve(){ 
    		b[1]=1;
    		for(int i=2;i<=n;i++){ //分阶段
    			maxlen = 0;
    			for(int j=i-1;j>=1;j--){ 
    				if(a[j]<a[i]&&b[j]>maxlen){ 
    					maxlen = b[j];
    					pre[i] = j;
    				}
    			}
    		    b[i] = maxlen+1;
    		}
    		
    		maxlen = b[1];
    		lab = 1;
    		for(int i=2;i<=n;i++)
    			if(b[i]>maxlen){ 
    				maxlen = b[i];
    				lab = i;
    			}
    		int i = lab;
    		int num = maxlen;
    		int j= maxlen;
    		while(num>0){ 
    			c[j] = a[i];
    			j--;
    			i = pre[i];
    			num--;
    		}
    	}
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=1;i<=n;i++)
    				a[i] = sc.nextInt();
    			solve();
    			for(int i=1;i<=maxlen;i++) { 
    				System.out.print(c[i] + " ");
    			
    			}
    			System.out.print("\n");
    		}
    	}
    }

# C.0-1背包 #

**题目描述**

*  给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为C。如何选择装入背包的物品，可以使得装入背包中物品的总价值最大？

**输入**

*  每组输入包括三行， 第一行包括物品个数n，以及背包容量C。 第二、三行包括两个一维数组，分别为每一种物品的价值和重量。

**输出**

*  输出包括两行，第一行为背包的最大总价值，第二行为所选取的物品。
 *  例如：最大总价值=15，物品选取策略为11001。
 *  数据保证答案唯一。

**样例输入 Copy**

5 10
    6 3 5 4 6
    2 2 6 5 4

**样例输出 Copy**

15
    11001

> 【代码老师讲过，书本上也有，就不多说啦，戳个链接——[戳我！戳我！][Link 2]】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void solve(int v[],int w[],int c,int m[][]){ 
    		int n = v.length-1;
    		int jMax = Math.min(w[n]-1, c);
    		
    		for (int j=0;j<=jMax;j++)
    			m[n][j] = 0;
    		for (int j=w[n];j<=c;j++)
    			m[n][j] = v[n];
    		
    		for (int i=n-1;i>=0;i--){ 
    			
    			jMax = Math.min(w[i]-1, c);
    			
    			for (int j=0;j<=jMax;j++)
    				m[i][j] = m[i+1][j];
    			for (int j=w[i];j<=c;j++)
    				m[i][j] = Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
    		}
    		
    // m[1][c] = m[2][c];
    // if (c>=w[1])
    // m[1][c] = Math.max(m[1][c], m[2][c-w[1]]+v[1]);
    		
    		
    	}
    	
    	public static void traceback(int [][]m,int w[],int c,int x[]){ 
    		int n = w.length-1;
    		for (int i=0;i<n;i++)
    			if(m[i][c]==m[i+1][c])
    				x[i] = 0;
    			else{ 
    				x[i] = 1;
    				c-=w[i];
    			}
    		x[n] = (m[n][c]>0? 1:0);
    		
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int c = sc.nextInt();
    			int v[] = new int[n];
    			int w[] = new int[n];
    			int x[] = new int[n];
    
    			for(int i=0;i<n;i++)
    				v[i] = sc.nextInt();
    			for(int i=0;i<n;i++)
    				w[i] = sc.nextInt();
    			
    			int [][]m = new int[n][c+1];
    			
    			solve(v,w,c,m);
    			traceback(m,w,c,x);
    			
    			System.out.println(m[0][c]);
    			for(int i=0;i<x.length;i++)
    			    System.out.print(x[i]);
    			System.out.println("\n");
    		}
    
    	}
    
    }
    
    //https://blog.csdn.net/ZHANGQIANYI2020/article/details/112509723

# D.X星人的基因 #

**题目描述**

*  X星人的基因由A、B、C、D、E五种不同的结构组合而成。  
    如果两个性别不同的X星人的基因序列相似度大于50%，按照X星的法律他们是禁止结婚的，等于50%据说还是可以的。  
    那么基因的相似度怎么计算呢？分别从两个人身上取长度均为N的基因片段，如果它们的最长公共子序列为M，则相似度=M/N。是不是很简单呢？  
    现在给你两段X星人的基因序列片段，请你判断他们是不是可以结婚？

**输入**

*  每一组测试数据包含3行， 第1行数字N表示待比较基因序列片段的长度，N<=10^3。 第2行和第3行为两个长度为N的基因序列片段。  
    输入0表示结束。

**输出**

*  两个X星人是否可以结婚，如果可以输出”Yes“，如果不可以输出”No“。

**样例输入 Copy**

8
    A B C D E A B C
    A C C D C B A E
    6
    A B C D E E
    A E D C B B
    0

> 【这个其实就是最长公共子序列的升级，求出最长公共子序列的长度，然后问题差不多就付出水面啦，但是我Java代码没抠出来，作业截止时间就还剩下1分钟，我就火急火燎的ctrl+c和ctrl+v了，对不起老师！/(ㄒoㄒ)/~~】

## 代码 ##

#include <bits/stdc++.h>
     
    using namespace std;
    const int cmax=1e3+15;
    int fac[cmax][cmax];
    string x,y;
    int main(){ 
        int n;
        while (~scanf("%d",&n)&&n!=0)
        { 
            memset(fac,0,sizeof(fac));
            char tt;
            int i,j;
              for (i=0;i<n;++i){ 
                cin>>tt;
                x+=tt;
                }
                  for (j=0;j<n;++j){ 
                    cin>>tt;
                    y+=tt;}
                  for (i=1;i<=x.size();++i){ 
                  for (j=1;j<=y.size();++j)
                    { 
                     if (x[i-1]==y[j-1]){ 
                     fac[i][j]=fac[i-1][j-1]+1;
                  } else{ 
                        fac[i][j]=max(fac[i][j-1],fac[i-1][j]);
                        }
                    }
            }
     
            int z=fac[x.size()][y.size()];
            if((double)z/n>0.5){ 
                cout<<"No"<<endl;
            } else
                cout<<"Yes"<<endl;
            x.clear();
            y.clear();
        }
        return 0;
    }

# E.出列人数 #

**题目描述**

*  有N位同学站在一排，体育老师要请其中的(N-K)位同学出列，将剩下的K位同学从左到右依次编号为1,2,3,…K，他们的身高分别为T1,T2,T3,…TK，要求满足T1<T2<T3<…<TK。已知N位同学的身高，请设计一个算法，计算最少需要几位同学出列可使得剩下的同学满足上述要求。

**输入**

*  多组输入，对于每一组测试数据，第1行N表示同学数量（n<=1000)。 第2行包含N个正整数，分别表示每一个同学的身高。（单位：厘米）

**输出**

*  输出最少需要出列的同学人数。

**样例输入 Copy**

4
    172 185 169 178
    5
    165 168 174 170 182

**样例输出 Copy**

2
    1

> 【这个是第一题最大递增子序列的长度的改版呀！只要发现其中规律，修改一下输出就OK了】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	public static int n,maxlen,max;
    	public static int []a = new int[105000];
    	public static int []b = new int[105000];
    	
    	public static void solve(){ 
    		b[1]=1;
    		max = 0;
    		for(int i=2;i<=n;i++){ //分阶段
    			maxlen = 0;
    			for(int j=i-1;j>=1;j--){ 
    				if(a[j]<a[i]&&b[j]>maxlen){ 
    					maxlen = b[j];
    				}
    			}
    		b[i] = maxlen+1;
    				
    		if(b[i]>max)
    			max = b[i];//存储最长递增子序列的长度
    		}
    	}
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			n = sc.nextInt();
    			for(int i=1;i<=n;i++)
    				a[i] = sc.nextInt();
    			solve();
    			System.out.println(n-max);
    		}
    	}
    }

# F.XP的午餐 #

**题目描述**

*  XP每天都会思考一个问题，今天午餐去哪里吃？这是一个很重要的问题，这会影响到他下午的体力值。他的午餐预算是M元，现在有N种菜品，每一种菜品的价格和能够提供的体力值已知（每种菜品只能选择一次），请问如何选择菜品能够让XP下午的体力值最大呢？

**输入**

*  多组输入 第一行：M元和菜品数量N。 接下来N行，每一行两个整数，分别表示每一种菜品的价格(vi)和能够获得的体力值(wi)。  
    （0<N<=20,0<=M<=1000）(0<=vi<=50，0<=wi<=100)

**输出**

*  最大体力值。

**样例输入 Copy**

10 5
    1 5
    2 4
    3 3
    4 2
    5 1

**样例输出 Copy**

> 【这个就是0-1背包那题的代码，输入的代码修改一下就过了，主要是别放反了数组，小编就是吃过这样的苦！/(ㄒoㄒ)/~~】

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void solve(int v[],int w[],int c,int m[][]){ 
    		
    		int n = v.length-1;
    		
    		int jMax = Math.min(w[n]-1, c);
    		
    		for (int j=0;j<=jMax;j++)
    			m[n][j] = 0;
    		for (int j=w[n];j<=c;j++)
    			m[n][j] = v[n];
    		
    		for (int i=n-1;i>=0;i--){ 
    			
    			jMax = Math.min(w[i]-1, c);
    			
    			for (int j=0;j<=jMax;j++)
    				m[i][j] = m[i+1][j];
    			for (int j=w[i];j<=c;j++)
    				m[i][j] = Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
    		}
    		
    // m[1][c] = m[2][c];
    // if (c>=w[1])
    // m[1][c] = Math.max(m[1][c], m[2][c-w[1]]+v[1]);
    		
    		
    	}
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int c = sc.nextInt();
    			int n = sc.nextInt();
    			int v[] = new int[n];
    			int w[] = new int[n];
    			int x[] = new int[n];
    
    			for(int i=0;i<n;i++){ 
    				w[i] = sc.nextInt();
    				v[i] = sc.nextInt();
    			}
    			
    			int [][]m = new int[n][c+1];
    			
    			solve(v,w,c,m);
    			System.out.println(m[0][c]);
    			
    		}
    
    	}
    
    }

> 【小编最近又迷上了一本新的漫画，真的很不错呀，o(*￣▽￣*)ブ，但是学习也不能落下呀，还是先吃饭吧，青椒炒肉吃了一勺青椒，/(ㄒoㄒ)/~~，食堂阿姨过分了吧，孩子还要长身体呀！】
> 
> > 句子君：
> 
> @要开心哦：“我明白这听上去很可笑，自己陪伴自己，自己疼爱自己，但是如果你是我，你就不会觉得可笑”  
> ——节选自《天才在左 疯子在右》中的其中一个故事（三只小猪）

[Link 1]: https://blog.csdn.net/qq_46546793/article/details/105615028
[Link 2]: https://blog.csdn.net/ZHANGQIANYI2020/article/details/112509723