题解 【P1004 方格取数】

· · 题解

看到题解里没有二维DP就补一发~

（有点沾沾自喜）

本蒟蒻的思路：

先跑一遍DP,

动态转移方程：f[i][j]+=max(f[i-1][j],f[i][j-1])，

然后对经过的点进行删除，

再跑一遍DP，

将两次的值相加即可得到答案。

（有点暴力见谅）

贴代码（码丑见谅）

#include<bits/stdc++.h>
using namespace std;
int n;
bool b;
int a[20][20];
int f1[20][20];
int f2[20][20];
int ans,ans2;
int x,y,z;
int main()
{
    cin>>n;
    while(cin>>x>>y>>z)
    {
        if(!x&&!y&&!z)//x y z均为0时退出
        {
            break;
        }
        f1[x][y]=z;//
        f2[x][y]=z;//直接赋值
    }
    for(int i=1;i<=n;i++)//DP求出第一条线路的最优解
    {
        for(int j=1;j<=n;j++)
        {
            f1[i][j]+=max(f1[i-1][j],f1[i][j-1]);//动态转移方程
        }
    }
    ans+=f1[n][n];//存入第一条线路的最优解
    ans2=ans;//防止ans被更改
    while(ans2>0)//倒序寻找被取的数第一个出现的位置，为0时即为取完
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(f1[i][j]==ans2)//当被取的数出现时
                {
                    ans2-=f2[i][j];//修改ans的值
                    f2[i][j]=0;//将这个点的值删为零
                    b=1;//打标记退出循环
                    break;
                }
            }
            if(b==1)
            {
                b=0;//防止只能退出一次
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)//DP求出第二条线路的最优解
    {
        for(int j=1;j<=n;j++)
        {
            f2[i][j]+=max(f2[i-1][j],f2[i][j-1]);//动态转移方程
        }
    }
    ans+=f2[n][n];//存入第二条线路的最优解
    cout<<ans;
    return 0;
}