题目描述

blablabla

样例

blablabla

DP

具体思路和Y总一样，就是改成了二维数组，i1与i2要从大值向小遍历

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=12;
int f[N][N];
int w[N][N];

int main()
{
    int n;
    cin>>n;

    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;


    for(int k=2;k<=2*n;k++)
    {
        for(int i1=k-1;i1>=1;i1--)
        {
            for(int i2=k-1;i2>=1;i2--)
            {
                int j1=k-i1;
                int j2=k-i2;
                if(i1<=n&&i2<=n&&j1<=n&&j2<=n)
                {
                     int t=w[i1][j1];
                     if(i1!=i2)t+=w[i2][j2];
                     int &x=f[i1][i2];
                     x=max(x,f[i1][i2]+t);
                     x=max(x,f[i1-1][i2-1]+t);
                     x=max(x,f[i1-1][i2]+t);
                     x=max(x,f[i1][i2-1]+t);

                }

            }
        }
    }

    printf("%d\n",f[n][n]);
    return 0;
}