当前位置:首页 > NOIP > 正文

NOIP 2000 方格取数

#include <bits/stdc++.h>
using namespace std;
/*
思路:
有来、回两次行走,而且不能有路径交叉。我们可以转换为一次行走,有两个人同时行走,形象地说为多线程。
只要每一时刻都保证两个人不在同一点上就可以保证路径不会交叉(这个仔细想想或者画一画就可以证明是对的)。
那么状态表示可以是f[i][j][k][l]表示第一个人在(i,j)第二个人在(k,l)时的最优解。
*/
int N;
int arr[100][100];
int f[15][15][15][15];
int main(){
    int a,b,c;
    cin>>N;
    cin>>a>>b>>c;
    while(a!=0&&b!=0&&c!=0){
        arr[a][b]=c;
        cin>>a>>b>>c;
    }
    
    
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=1;k<=N;k++){
                for(int l=1;l<=N;l++){
                    int tmp1=max(f[i][j-1][k][l-1],f[i-1][j][k][l-1]);
                    int tmp2=max(f[i][j-1][k-1][l],f[i-1][j][k-1][l]);
                    f[i][j][k][l]=max(tmp1,tmp2)+arr[i][j];
                    if(i!=k&&j!=l){
                        /*不在同一个点上*/
                        f[i][j][k][l]+=arr[k][l];
                    }
                }
            }
            
        }
    }
    cout<<f[N][N][N][N];
    
    
        
    return 0;
    
    
}


更新时间 2019-03-30

有话要说...