E2-A
E2-A 此处即是勇者试炼之殿堂
题目描述
小 AAA 正在勇闯算法分析与设计！
小 AAA 需要先挑战 nnn 周的比赛才能挑战期末考试。第$ i$ 周（1≤i≤n）（1≤i≤n）（1≤i≤n）有一场上机赛和一场练习赛，难度值分别为 Ci,EiC_i,E_iCi,Ei。
小 AAA 初始的能力值为 AAA，每一周小 AAA 可以选择两场比赛中至少一场 AKAKAK。如果小 AAA 的能力值不小于比赛的难度值，那么小 AAA 能顺利 AKAKAK 比赛并通过挑战。在一周所有比赛结束后，小 AAA 的能力值可以得到相当于 AKAKAK 比赛难度值之和的提升。如果小 AAA 这一周无法 AKAKAK 任何一场比赛，那么小$ A$ 这一周挑战失败，无法继续接下来的挑战。
小 AAA 需要你帮忙计算，他最多能通过多少周的挑战。
输入
第一行，一个正整数 T（1≤T≤100）T（1≤T≤100）T（1≤T≤100），表示数据组数。
对于每组数据：
第一行，两个整数 n,A（1≤n≤104,−109≤A≤109）n,A（1≤n≤10^4,−10^9≤A≤10^9）n,A（1≤n≤104,−10 ...
C3-I
C3-I 子序列个数
题目描述
给出一个长度为 nnn 的仅包含小写英文字母的字符串 sss，数一数 sss 有多少个子序列为 buaa。
形式化的，你需要统计以下四元组的数量：(a,b,c,d)(a,b,c,d)(a,b,c,d) 满足 1≤a<b<c<d≤n1≤a<b<c<d≤n1≤a<b<c<d≤n 且 sas_asa= b，sbs_bsb= u，scs_csc=sds_dsd= a。
输入
一行一个字符串表示 sss，保证 1≤n≤1051≤n≤10^51≤n≤105。
输出
一行一个整数表示答案。
题目分析
用一个二维数组dp[i][j]dp[i][j]dp[i][j]表示sss的前iii个字符中以ttt的前jjj个字符作为子序列的个数，答案即为dp[lenS][4]dp[lenS][4]dp[lenS][4]。
dp[0][0]=1,dp[i][0]=1,dp[0][j]=0dp[0][0]=1,dp[i][0]=1,dp[0][j]=0dp[0][0]=1,dp[i][0]=1,dp[0][j]=0
当s[i− ...
C3-F
C3-F 最长公共子串和最长公共子序列
题目描述
给定两个仅包含小写英文字母的字符串 S1S_1S1，S2S_2S2，试求二者最长公共子串的长度，以及二者最长公共子序列的长度。
我们称 AAA 是 SSS 的子串，当且仅当 A 可由 S 删去一段前缀与一段后缀得到，例如 dest 和 star 都是 jadestar 的子串，而 jar 不是。
我们称 AAA 是 SSS 的子序列，当且仅当 A 可由 S 删去一些字符得到，例如 jet 和 jar 都是 jadestar 的子序列，而 rest 不是。
我们称 AAA 是 S1S_1S1 与 S2S_2S2 的公共子串，当且仅当 AAA 既是 S1S_1S1 的子串又是 S2S_2S2 的子串。
我们称 AAA 是 S1S_1S1 与 S2S_2S2 的公共子序列，当且仅当 AAA 既是 S1S_1S1 的子序列又是 S2S_2S2 的子序列。
输入
本题测试点包含多组数据。
第一行，一个正整数 T（1≤T≤10）T（1≤T≤10）T（1≤T≤10），表示数据组数。
对于每组数据：
第一行，一个字符串 S1（1≤∣ ...
C3-D
C3-D 导弹轰炸
题目描述
AAA 国有 nnn 个前哨站，每个前哨站有一个重要程度 wiw_iwi，现在你是 BBB 国的总指挥，想要使用你们的导弹轰炸$ A$ 国的前哨站。可惜的是BBB 国的导弹在轰炸相邻的两个前哨站会产生干扰导致导弹失效。
现在你想知道在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值为多少。
输入格式
第一行包含一个整数$ t$ ，表示测试数据的数量，接下来 ttt 组测试数据。
每组测试数据包含两行。
第一行包含一个正整数 n(2≤n≤105)n(2≤n≤105)n(2≤n≤105)，含义如上。
第二行包含 nnn 个正整数 w1,w2,…,wn(1≤wi≤105)w_1,w_2,…,w_n(1≤w_i≤105)w1,w2,…,wn(1≤wi≤105)，表示每个前哨站的重要程度。
数据保证 ∑n≤4⋅105∑n≤4⋅10^5∑n≤4⋅105 。
输出格式
对于每组测试数据，输出一行一个整数，表示在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值。
题目分析
先从1个站台考虑，此时答案为w1w_1w1；当有2个站台时，答案 ...
C3-C
C3-C 矩阵连乘
题目描述
nnn个矩阵连乘，求有多少种乘法P(n)P(n)P(n)？
输入
一个正整数nnn，表示矩阵个数，1≤n≤351≤n≤351≤n≤35。
输出
$1∼n $个矩阵连乘，分别有多少种乘法。
题目分析
将nnn个矩阵分为两部分i,n−ii,n-ii,n−i则：
P(n)=∑P(i)∗P(n−i)P(n)=\sum P(i)*P(n-i)
P(n)=∑P(i)∗P(n−i)
示例代码
123456789dp[1]=1;dp[2]=1;for (int i = 3; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j] * dp[i - j]; } }
C3-B
C3-B 钢管切割
题目描述
给定一段长度为nnn英寸的钢管和一个价格表，该价格表表示长度为$ i（i=1,2,\ldots,n）英寸的钢管的价格为英寸的钢管的价格为英寸的钢管的价格为p_i$。求钢管切割方案，使得总销售价格最大，注意钢管的长度必须为整英寸。
输入
第一行一个正整数 n（1≤n≤104）n（1 \le n \le 10^4）n（1≤n≤104），表示钢管的总长度。
第二行nnn个正整数 p1,p2,…,pn(1≤pi≤107)p_1,p_2,…,p_n(1≤pi≤10^7)p1,p2,…,pn(1≤pi≤107)，表示钢管的价格。
输出
第一行一个正整数，表示最大总销售价格。
第二行一个正整数 kkk，表示钢管被分割成 k 段。
第三行kkk 个正整数 a1,…,aka1,…,aka1,…,ak，表示钢管的分割方式，需保证$ ∑a_i=n$
如果有多种分割方案，输出任意一种即可。
题目分析
求切割方案，即求销售价格最大的子状态。设dp[i]dp[i]dp[i]为钢管长iii时最大价格。可得状态转移方程如下：
dp[i]=max(p[i],dp[1]+p[i−1], ...
