G7007 [GESP202409 七级] 矩阵移动 题解

知识点：动态规划、网格路径、资源约束。

解题思路

滚动DP记录到当前格、使用k次问号变1后获得的最大1数量。来自上方或左方取最大，1格加1，问号可不使用资源或消耗一次加1。

为什么正确

所有单调路径最后一步只有上或左，资源使用数完整描述剩余约束，逐格枚举两类选择穷尽可行路径。

易错点

问号的资源维度倒序更新，防止同格被使用多次；起点和终点的格子收益都要计入。

复杂度

时间O(nmx)，空间O(mx)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n,m,x;
        cin>>n>>m>>x;
        vector<string>a(n);
        for(auto &s:a)cin>>s;
        vector<vector<int>>dp(m,vector<int>(x+1,-1000000));
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) {
            vector<int>v(x+1,-1000000);
            if(i==0&&j==0)v[0]=0;
            else for(int k=0;k<=x;k++)v[k]=max(i?dp[j][k]:-1000000,j?dp[j-1][k]:-1000000);
            if(a[i][j]=='1')for(auto &z:v)z++;
            else if(a[i][j]=='?')for(int k=x;k>0;k--)v[k]=max(v[k],v[k-1]+1);
            dp[j].swap(v);
        }
        cout<<*max_element(dp.back().begin(),dp.back().end())<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。