真题解析

【题目大意】在一个n*m的矩阵中从(1,1)到(n，m)移动，只能向下或者向右移动，矩阵中有1和0，还有？，在移动的过程中尽可能的拿到1，可以将矩阵中的x个？修改成1，使得最后拿到的1尽可能的多。

【考纲知识点】动态规划

【解题思路】如果不考虑x,问题转换成为从(1,1)到(n，m)只能向下或者向右移动最多拿到多少个1。对于矩阵中的任意一点(i,j)只可能从(i-1,j)或者(i,j-1)移动过来。

状态设计：dp[i][j]表示到达位置(i，j)时可以获得的最大分数。

不难得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (a[i][j] == ‘1’？1:0)。

考了加入x,还是只能向下或者向右移动，之前只有1对结果有贡献，现在？也对结果有贡献。由于x的限制，？不能无限制的修改成1，所以需要记录修改次数。设计状态时增加一维表示修改次数。

状态设计：dp[i][j][k]表示到达位置(i,j)时，已经修改了k个字符所能获得的最大分数。

如果a[i][j]是0或者1，正常转移，和不考虑x时的转移过程一致，如果a[i][j]是？，先考虑当前有没有修改次数，如果没有当前阶段拿到和1和上一阶段比较求最大值，如果有修改次数，，需要看之前修改转移的值是多少，求最大值。

当a[i][j] == 1时，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1,

当a[i][j] == 0时，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

当a[i][j] == ?时，如果没有修改次数，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

如果有修改次数，再考虑改或不改。

若修改当前节点为1，则有dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1,

若不修改，则有dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

取以上情况的最大值即可，同时需要考虑，若k==x,则不可增加修改次数。

可以观察到每一行的计算只依赖于上一行的信息，第一维可以优化，故可以使用滚动数组对数组进行降维。

【参考程序】