百度笔试编程题小红操作01序列

只看到了题目，口糊了一个做法供大家讨论，如果有正解了求求踢我一下我也好奇，遍历原串s，dp[i][j][k]代表到第i位为止，已经进行了j次修改，到i为止（包含i）有k个0的情况下得到的收益，那么对于一组确定的ijk，收益也是确定的，答案为dp数组在i=n时的max，状态转移部分第i项只会用到第i-1项，所以可以省略i这一维度滚动优化，同时使用map只维护合法解来避免n^3遍历i*j*k，那么其实只有四种情况，状态转移如下 当前位是0不变，ndp[j][k+1]=dp[j][k]; 当前位是1不变，ndp[j][k]=dp[j][k]+k; 当前位是0改变，ndp[j+1][k]=dp[j][k]+k; 当前位是1改变，ndp[j+1][k+1]=dp[j][k]; 因为如果当前位最终是0，那么只会让k+1，答案直接继承，如果当前位最终是1，会与之前的所有0构成01子序列，会对答案提供k个贡献 检查一下发现n是3000复杂度合理，维护方式不止这一个，也可以提前预处理出原串到第i位有多少个0，dp[j][k]代表到第i位修改了j个1，k个0，应该也是合法的

只过了23%😂