算法1

(暴力枚举) $O(n^4)$

直接枚举所有的走法

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int f[N][N][N][N],w[N][N];//ij代表第一个人走的位置，i1j1代表第二个人走的位置
int main()
{
    int n;
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if(a==0&&b==0&&c==0) 
            break;
        w[a][b]=c;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int i1=1;i1<=n;i1++)
                for(int j1=1;j1<=n;j1++)
                {
                    int t1=w[i][j],t2=w[i1][j1];
                    if(i==i1&&j==j1) t1=0;
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1-1][j1]+t1+t2);
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1][j1-1]+t1+t2);
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i][j-1][i1-1][j1]+t1+t2);
                    f[i][j][i1][j1]=max(f[i][j][i1][j1],f[i-1][j][i1][j1-1]+t1+t2);
                }
    cout<<f[n][n][n][n];
    return 0;
}

算法2

(暴力枚举) $O(n^3)$

将f[i][j][i1][j1]转化为f[k][i][i1],这样可以少枚举一个for循环

时间复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=12;
int f[N+N][N][N],w[N][N];
int main()
{
    int n;
    int a,b,c;
    cin>>n;
    while(cin>>a>>b>>c)
    {
        if(a==0&&b==0||c==0)
            break;
        w[a][b]=c;
    }
    for(int k=2;k<=n+n;k++)
    {
        for(int i=1;i<=n;i++)
            for(int i2=1;i2<=n;i2++)
            {
                int j=k-i,j2=k-i2;
                int t=w[i][j];
                if(i!=i2) t+=w[i2][j2];
                if(j>=1&&j<=n&&j2>=1&&j2<=n)
                {
                    f[k][i][i2]=max(f[k][i][i2],f[k-1][i-1][i2-1]+t);
                    f[k][i][i2]=max(f[k][i][i2],f[k-1][i-1][i2]+t);
                    f[k][i][i2]=max(f[k][i][i2],f[k-1][i][i2-1]+t);
                    f[k][i][i2]=max(f[k][i][i2],f[k-1][i][i2]+t);
                }
            }
    }
    cout<<f[n+n][n][n];
    return 0;
}