本题给定了0和1的数量，让你如何排列才能使分数最优。我们先考虑问题的简单版本，如果给定字符串t全为问号，即对组成的字符串不加限制，就转变经典传纸条问题，即只求一条从(0,0)到(cnt0,cnt1)的路径，只能向右或向下走，使得路径上的点的权值和最大。显而易见的变化中的量就是坐标(x,y)，用dp[
展开全文
把过程看作是从（0,0）到（c0，c1）的过程，1表示向右走，0表示向下走， maxx【i】【j】表示i个0，j个1的最高得分 minn【i】【j】表示i个0，j个1的最低得分 sum【x】表示标准串s，到第x位置为止共有多少1 满足s与t前缀x1同等价于sum【x】==j，后缀x1+1~n同就等价
展开全文
solution 考虑dp。用表示对于t的前个位置，有个位置为1最小得分。 显然当前面1的个数确定之后，后面1的个数也确定了。也就是我们可以计算对于位置它的前缀是否和s相似，它的后缀是否和s相似，然后就可以计算出i位置的贡献。枚举i位置是'0'还是'1'转移即可。 code /*
* @Author
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
