第三题
题目大意
给出nnn对数字,我们称第iii对为ai,bia_i,b_iai ,bi 。
现在你可以进行nnn次的选择,每次可以选择aia_iai 与bib_ibi 其中一个,选A获得一个字符H,选B获得一个字符T代表方案,若获得他们的数字累加起来,最后的结果刚好等于sumsumsum,那么输出Yes与你的选择方案,否则输出No。
求解是否有这样的选择方案?
思路解析
第一眼看过去,20%的数据范围n<7n < 7n<7。非常方便,假如我们将每一次选择的方案搭配全部枚举出来,那么也就是求1 n1~n1 n种选择的全排列,那么递归就可以实现。
1. 递归求解全排列
2. 判断是否符合sum决定输出内容
时间复杂度大约为O(2n)O(2^n)O(2n)
观察100%的数据,n的最大取值为100,那么递归枚举全排列的方式就不再合适。但是我们也可以观察到,分数sum最大为10000,那么我们可以尝试着使用 动态规划 来求解。
动态规划的时间复杂度为O(n×sum)O(n \times sum)O(n×sum),符合题目要求,紧接着来设计状态。
我们的目的是为了判断是否存在方案可以满足sum的条件,那么使用动态规划来求解的时候,我们可以从起点开始衍生枚举出每一个状态方案的数值,并且每个顶点只遍历一次,符合题目要求,故选择动态规划。
1. 设置状态: 我们设置dp[i][j],代表在选取了i个卡牌的时候,数值为j的状态。 那么最后的答案则为dp[n][sum]。假若dp[n][sum]存在,那么则有答案。 因此我们需要给dp[i][j]上变量flag与string,保存当前字符是否存在且方案的排列。
2. 状态转移方程 :
对于dp[i][j]来说,他有两种方法可以到达。
1. 选择正面: 从dp[i-1][j-a[i]] 加一张正面卡牌a[i]a[i]a[i]到达dp[i][j]。
2. 选择反面: 从dp[i-1][j-b[i]]加一张反面卡牌b[i]b[i]b[i]到达dp[i][j]
假若存在方法可以到达,则flag为true,string累加对应方案的字符