블루 브리지 컵 알고리즘 트레이닝 체크 수 By Assassin [다중 스레드 dp]

     
　　  N*N    (N<=10),                ,            0。
　　         A  (1,1)  ，      ，      ，        B (N,N)。      ，          （            0）。
　　   A  B      ，   2      ，           。
    
　　           N（  N*N    ），           ，       ，             。     0      。
    
　　        ，  2           。
    
　　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
    
　　67

#include
using namespace std;
int dp[11][11][11][11]={0};
int mapp[11][11]={0};
int n;
int dp_go(int x1,int y1,int x2,int y2){
    if(x1==x2&&y1==y2){
        return mapp[x1][y1];
    }
    else{
        return mapp[x1][y1]+mapp[x2][y2];
    }
}


int main(){
    int temp1,temp2,pos;
    scanf("%d",&n);
    while(1){
        scanf("%d%d%d",&temp1,&temp2,&pos);
        if(temp1==0&&temp2==0&&pos==0) break;
        mapp[temp1][temp2]=pos;
    }
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=n;y1++){
            for(int x2=1;x2<=n;x2++){
                for(int y2=1;y2<=n;y2++){
                    dp[x1][y1][x2][y2] = max(max(dp[x1-1][y1][x2-1][y2], dp[x1-1][y1][x2][y2-1]),
                                             max(dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1]));
                    dp[x1][y1][x2][y2]+=dp_go(x1,y1,x2,y2); 
                }
            }
        }
    }
    cout<return 0;
}