[数据结构与算法] 提高课二刷疑难杂题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 提高课二刷疑难杂题 -> 正文阅读

[数据结构与算法]提高课二刷疑难杂题

方格取数

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int g[N][N];
int f[2*N][N][N]; // 假设有两个小朋友在同时从A走向B，g[k][i1][i2]=w,表示第一个小朋友
//走到第(i1,k-i1),第二个小朋友走到(i2,k-i2)时的最小值为w
int main(){
    int n;
    cin >> n;
    int a,b,c;
    while(cin>>a>>b>>c,a){
        g[a][b]=c;
    }
    for(int k=2;k<=2*n;k++){//从A走到B必然要走2*n-2次（曼哈顿距离）,k要从2开始因为一步没走时在（1，1）点
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                int j1=k-i1,j2=k-i2;
                if(j1<=n&&j1>=1&&j2<=n&&j2>=1){
                    //我们惊奇的发现，两人可能同时到达同一格子，这时只取一次t就行了
                    //不可能出现1人走到了另一人已经走过的格子上这种情况
                    int &x=f[k][i1][i2];
                    int t = g[i1][j1];
                    if(i1!=i2) t += g[i2][j2];
                    x = max(x, f[k-1][i1-1][i2-1]+t);
                    x = max(x, f[k-1][i1-1][i2]+t);
                    x = max(x, f[k-1][i1][i2-1]+t);
                    x = max(x, f[k-1][i1][i2]+t);
                }
            }
        }
    }
    cout << f[2*n][n][n] << endl;
    return 0;
}