Tag: DP

百度之星第三场 – BD202317 石碑文

题目链接题目链接题目大意给你一个长度为n的字符串，问你有多少个连续shs三个及三个以上的字符串种类题解状态压缩dp dp状态为dp[i,j]含义为第i个字符，凑了j个shsshsshs的第几个字符结尾为s的时候，可以加s凑成s结尾，加h凑成sh,随…

Solost2023 年 10 月 05 日0 条评论

题目连接链接题目大意有N个物品，0物品无毒，1物品有毒，你不能连续吃两次有毒的东西，吃完没毒的就会从前一种状态转移到现在吃的东西的状态，问你吃了的东西的总价值是多少。题解刚开始想的是双指针扫描，但是会有一个问题，如果前面选的是0，现在选了一个1，可能…

Solost2023 年 06 月 25 日0 条评论

题目链接链接题目大意有n个座位，给一个数列，1代表有人，0代表没人，让所有人坐到其他没人的地方去，移动的花费是位置的差值，问你最少的花费是多少？题解这道题第一个想法是把第一个人安排到自己前面所有空的地方，然后就有很多种安排方法，然后第二个人再安排到第…

Solost2023 年 05 月 17 日0 条评论

题目连接题目链接参考链接参考链接参考链接题解思路应该是计算出要加的左括号数目，然后再镜像字符串计算出需要添加右括号的数目，相乘即可。因为让他变成一个合法的字符串需要左括号的数目大于等于右括号的字符串，我们第一次可以计算出使得右括号一定有的匹配的方法…

Solost2023 年 03 月 23 日0 条评论