p1004方格取数

p1004方格取数

题目描述
设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B

某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

输入格式
输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。

输出格式
只需输出一个整数，表示 2 条路径上取得的最大的和。

输入输出样例
输入 #1
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出 #1
67

说明/提示
NOIP 2000 提高组第四题

其实是我都有在想要不要发博客 水水数量 ，因为这个洛谷上有题解，写博客出来好像没什么意思。

思路也不是自己想的，是看了其他大佬的代码才想到的，最开始只想到了bf的方法，实在惭愧。

我发现，现在想问题还是很容易去暴力，去枚举，这种办法几乎算不上办法，主要原因是因为自身代码量不足，思路不够开阔，题做少了。对的就是这样

代码：

下面的代码应该很好看懂，就不写注释了

//
//  main.cpp
//  Problem
//
//  Copyright © 2020 Kylin. All rights reserved.

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <bitset>
#include <set>
/*
#include <unistd.h>		//包含<unistd.h>
#include <sys/types.h>	//包含<sys/types.h>
 */
#pragma GCC optimize("Ofast")


using namespace std;
#define ll  long long
#define lowbit(x) (x)&(-x)
#define print_str(a) do{for(int i=0;i<strlen(a);i++)printf("%c",a[i]);printf("\n");}while(0)
#define ms(a,b) memset(a,b,sizeof a)

const int N = 11;
int n,m,g[N][N];
int f[N][N][N][N];

int main()
{
    int a,b,c;
    scanf("%d",&n);
    
    while (scanf("%d%d%d",&a,&b,&c)&&(a+b+c))
        g[a][b] = c;
    
    int i,j,k,l;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        for(k=1;k<=n;k++)
        {
            l=i+j-k;
            if(l<=0)
                break;
            f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])));
            if(i==k&&j==l)
                f[i][j][k][l]+=g[i][j];
            else
                f[i][j][k][l]+=g[i][j]+g[k][l];
        }
    cout<<f[n][n][n][n]<<endl;
    
    return 0;
    
}

等我过段时间了把后面O(n^2)的搞明白了再把代码续上来。

算了算了 直接写上来吧。 估计我后面也不会想。
以下代码直接复制的AC代码
附上题解
这里的题解确实有意思，有dp的，搜索的，说实话我都想到过这两种。
但我没有想到的是用SPFA，费用流来解。
我自己觉得上图论里那些算法和搜索是一样的，所以有SPFA也不应该意外。关键还是自己图论没学透

#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
    int x,y,data;//记录每个点的位置和数值
}p[100];
int n,m,map[11][11],f[11][11];
int main()
{
    int i,ii,j,jj,l;
    scanf("%d",&n);
    while(1)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!a&&!b&&!c)
            break;
        p[++m].x=a;
        p[m].y=b;
        p[m].data=c;
    }
    for(i=1;i<=m;i++)
        map[p[i].x][p[i].y]=p[i].data;
    for(l=2;l<=n*2;l++)//每个点最少横着竖着都走一格，最多都走n格就到终点
        for(i=l-1;i>=1;i--)//和前面说的一样，倒着做
            for(ii=l-1;ii>=1;ii--)
            {
                j=l-i;jj=l-ii;//i+j=ii+jj=l
                f[i][ii]=max(max(f[i][ii],f[i-1][ii-1]),max(f[i-1][ii],f[i][ii-1]))+map[i][j];
//重点说明一下吧，这里省略了很多。如果i不减1，意思就是j-1，因为上一个阶段就是l-1嘛。如果ii-1，意思就是说jj不减1。
                f[i][ii]+=map[ii][jj]*(i!=ii);
//如果i==ii，其实就是(i==ii&&j==jj)，因为和都是l嘛。如果走过一遍，第二遍走得到的值就是0（题目上说的）。
            }
    printf("%d\n",f[n][n]);
//输出意思是在路径长度为2*n的阶段，两遍都走到(n,n)的最优值。因为在这里(j=2*n-i=n,jj=2*n-ii=n),所以走到的就是(n,n)的位置
    return 0;
}