深信服笔试8.18

被橄榄了

• 1. dp。设f[i][j]为s串到i位置，t串到j位置的最大匹配数。先预处理每一个*的上一个字符是什么，再处理s串每个字符前面连续重复的有几个记为cnt[i]，fij转移分情况，如果t[j]=='*',那么转移就是f[i][j] = max(f[i-cnt[i]][j - 1] + cnt[i] , f[i][j-1])。si为其他字母就是f[i][j] = max{f[i-1][j],f[i][j-1],f[i-1][j-1] + s[i] == t[j]};
• 2. dp，f[i] = max(f[i] , f[last ]+ a[i]) 。1<=last <= i-k 。用前缀max来优化。f[i] = a[i] + pre[i-k], pre[i]=max(pre[i-1],f[i]);
• 3.不给数据范围真的sb，直接跑了个阶乘枚举求最大值。这题应该没有多项式做法吧