NEUQ-ACM预备队week7

公司专注于为企业提供成都网站制作、成都网站建设、微信公众号开发、成都做商城网站，小程序开发，软件按需规划网站等一站式互联网企业服务。凭借多年丰富的经验，我们会仔细了解各客户的需求而做出多方面的分析、设计、整合，为客户设计出具风格及创意性的商业解决方案，创新互联更提供一系列网站制作和网站推广的服务。文章目录

• • NEUQ-ACM预备队week7
  • • 1.采药(P1048)(01背包模板题)
    • 2.最长上升子序列(B3637)(模板题)
    • 3.大子段和(模板)
    • 4.最长公共子序列

1.采药(P1048)(01背包模板题)

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);
        int T = sc.nextInt();
        int n=sc.nextInt();
        int[] weight = new int[105];
        int flag=0;
        int[] value = new int[105];
        while (sc.hasNext()){weight[flag]=sc.nextInt();
            value[flag]=sc.nextInt();
            flag++;
        }
        testweightbagproblem(weight, value, T);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i<= wlen; i++){dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i<= wlen; i++){for (int j = 1; j<= bagsize; j++){if (j< weight[i - 1]){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]);
                }
            }
        }
        System.out.println(dp[wlen][bagsize]);
    }
}

2.最长上升子序列(B3637)(模板题)

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

(c++版懒得写了,很好改)

import java.util.Arrays;
import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//吃掉
        int[] nums=new int[n];
        int flag=0;
        while(sc.hasNext()){nums[flag++]=sc.nextInt();
        }
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 0; i< dp.length; i++) {for (int j = 0; j< i; j++) {if(nums[i]>nums[j]){dp[i]=Math.max(dp[i],dp[j]+1);//与前面每一个比较,不是dp[i]与dp[j]+1比较
                }
            }
        }
        int res=0;
        for (int i = 0; i< dp.length; i++) {res=Math.max(res,dp[i]);
        }
        System.out.println(res);
    }
}

3.大子段和(模板)

思路:

dp[i]：包括下标i之前的大连续子序列和为dp[i]

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

import java.util.Scanner;
public class p1115 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//吃掉
        int[] nums=new int[n];
        int flag=0;
        while(sc.hasNext()){nums[flag++]=sc.nextInt();
        }
        int[] dp=new int[nums.length];

        if (nums.length == 0) {System.out.println(0);
        }
        
        int res = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i< nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res >dp[i] ? res : dp[i];
        }
        System.out.println(res);
    }
}

4.最长公共子序列

思路:先计数,再还原

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

确定递推公式

主要就是两大情况：text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

• 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
• 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

#includeusing namespace std;
#define int long long
int n,m,f[5005][5005],vis[5005][5005];
char s[5005],t[5005],ans[5005];
signed main(){
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1),m=strlen(t+1);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(s[i]==t[j]){
				f[i][j]=f[i-1][j-1]+1;
			}else{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
		}
	}	
	int i=n,j=m;
	while(f[i][j]>0){
		if(s[i]==t[j]){
			ans[f[i][j]]=s[i],i--,j--;
		}else{
			if(f[i][j]==f[i-1][j])i--;
			else j--;
		}
	}
	printf("%s",ans+1);
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：NEUQ-ACM预备队week7-创新互联
本文来源：http://scgulin.cn/article/ijpjs.html