牛客假日团队赛10 A 方格取数（简单的动态规划）

   简单说一下题意，给一个矩阵，矩阵上绝大多数数字为0，其余一些数字不为0（为正整数），找出两条条从左上角到右下角的路径，使得数字最大，每条路径只可以向右和向下，且第一条路径走过后，数字变为0。

   自己起初隐隐感觉是动态规划，后来也不知道怎么搞，后来看了题解，才恍然大悟，这里说一下自己的理解。

   既然是两条路径，我们不妨让两条路径同时出发，假设第一条路径走到了点A(i,j),第二条路径走到了点B(k,l),既然是两条路径同时出发，我们令dp[i][j][k][l]为第一条路径走到A点，第二条路径走到B点的最大值。由于只有两个行走方向，易得:

   dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]);

   由于本题的数据范围不大，矩阵最大10*10，所以直接四重循环暴力求解就可以了。下面贴下我的代码（自己开了long long，其实没有必要）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15][15][15];
ll mmap[15][15];
int main(){
    ll t;
    ll x,y,num;
    scanf("%lld",&t);
    memset(dp,0,sizeof(dp));
    memset(mmap,0,sizeof(mmap));
    while(~scanf("%lld%lld%lld",&x,&y,&num)&&(x+y+num)){
        mmap[x][y]=num;
    }
    for(ll i=1;i<=t;i++)
        for(ll j=1;j<=t;j++)
            for(ll k=1;k<=t;k++)
                for(ll l=1;l<=t;l++){
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]),max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+mmap[i][j];
                   // mmap[i][j]=0;
                    if(i!=k||j!=l){
                        dp[i][j][k][l]+=mmap[k][l];
                 //       mmap[k][l]=0;
                    }
                }
    cout<<dp[t][t][t][t];
    return 0;
}