T1 ------必做题------
非正题,输出1即可
T2 最佳球队组建
可以针对其进行sort的排序,然后对其构成子序列,并求出其中值最大的。即可视年龄为序,求出不降序的最大子序列。若合法利用动态转移方程:dp[i]=max(dp[i],dp[j]+p[i].second);
样例代码
T3 信封问题
因为[1]只能装其他信封,被[1]装的只能去[1]信封或其他信封,则产生a[n-1]和a[n-2]种情况,而[1]能去产生这种情况n-1次所以得(a[i-1]+a[i-2])*(i-1)种。
样例代码
T4 神秘的礼物
可以对信封进行 sort 排序,然后对其构成递增子序列,并求出其中长度最长的子序列。即宽度,高度同时满足递增要求,求出最长子序列。
样例代码
T5 挖地雷
mp保存是否连接,再求出最大子序列,动态转移方程:dp[i]=max(dp[i],dp[j]+a[i]);
样例代码
T6 数字连线游戏
两行数字中,数值相等且位置顺序合法的数字进行配对,不相交则下标递增,实际就是求两行数字的最长公共子序列。动态转移方程:dp[i][j]=dp[i-1][j-1]+1;dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
样例代码
T7 ------选做题------
非正题,输出1即可
T8 古老卷轴的修复 (真是 普及-吗)
可以先求出两个字符串的最长公共子序列,再通过最长公共子序列得出最短公共超序列(直播说的是这个名吧?)。动态转移方程:dp[i][j]=dp[i-1][j-1]+1;max(dp[i-1][j],dp[i][j-1]);
样例代码
T9 单词的最小修改
可以先求出两个字符串的最长公共子序列,输出剩下的字符数。动态转移方程:dp[i][j]=dp[i-1][j-1]+1;dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
T10 大师
这题不会!啊啊啊啊啊!我写的是题解里的代码:《26年春季星光提高班第5课讲义.PDF》。老师教一下。
原讲义代码