方格取數

題目:

#include <bits/stdc++.h>
using namespace std;
int a[20][20];
int f[40][20][20];
int main()
{
    int n;
    cin>>n;
    while(1)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(u==0&&v==0&&w==0) break;
        a[u][v]=w;
    }
    for(int k=2;k<=2*n;k++)
    {
        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)
                {
                    int c=a[i1][j1];
                    if(i1!=i2) c+=a[i2][j2];
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+c);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+c);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+c);
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+c);
                }
            }
        }
    }
    cout<<f[2*n][n][n]<<endl;
    return 0;
}