问题标题: 洛谷：P1005 [NOIP2007 提高组] 矩阵取数游戏

样例没过，记忆化搜索+区间DP+idx搜寻大招（本来以为要用二分找，后来发现inf小，不需要），菜鸡求助

#include <iostream>
#include <cstring>
#include <cmath>
#define inf 85

using namespace std;

int n, m, a[inf][inf], f[inf], vis[inf][inf], ans;

int down_find(int hang) {
    for(int i=m; i>=1; i--)
        if(vis[hang][i])
            return i;
    return 0;
} 

int up_find(int hang) {
    for(int i=1; i<=m; i++)
        if(vis[hang][i])
            return i;
    return 0;
} 

int dfs(int x) {
    if(f[x] != -1) return f[x];
    if(x > n) return f[n];
    bool flag = false;
    int idx_A = up_find(x), idx_B  = down_find(x);
    // cout << idx_A  << " " << idx_B << endl;
    int Plan_A = dfs(x+1) + a[x][idx_A]*pow(2, x);
    int Plan_B = dfs(x+1) + a[x][idx_B]*pow(2, x);
    if(idx_A == 0) {
        vis[x][idx_B] = false;
        f[x] = Plan_B;
    } else if(idx_B == 0) {
        vis[x][idx_A] = false;
        f[x] = Plan_A;
    } else if(Plan_A > Plan_B) {
        vis[x][idx_A] = false;
        f[x] = Plan_A;
    } else {
        vis[x][idx_B] = false;
        f[x] = Plan_B;
    }

    return f[x];
}

int main(){
    memset(vis, true, sizeof(vis));
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    while(m--) {
        memset(f, -1, sizeof(f));
        ans += dfs(1);
    }
    cout << ans;
    return 0;
}

开了复制了，方便各位大佬调试

我的方法跟题解不一样，发网址的一律拒绝采纳

@臧鸿志 @汪恺恒 @崔竣恺 @侯平仄 @赵逸凡 @黄依成