三取方格数------多进程dp

 2008-12-05 19:27

#include<iostream>
using namespace std;
int n,value[21][21],f[40][21][21][21];
int k,xa,xb,xc,i,j,t;
void calc1();
void calc2();
void dp();
int main(void){
    cin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>value[i][j];
           
    f[1][1][1][1] = value[1][1];
    dp();
   
    cout<<f[2*n-1][n][n][n];
   
    system("pause");
    return 0;
}
   
void dp(){
     for(k=2;k<=n;k++)
         for(xa=1;xa<=k;xa++)
         for(xb=1;xb<=k;xb++)
         for(xc=1;xc<=k;xc++){
             calc1();
             f[k][xa][xb][xc] = t;
            
             calc2();
             f[k][xa][xb][xc] += t;
         }
     
     for(k=n+1;k<=2*n-1;k++)
         for(xa=k-n+1;xa<=n;xa++)
         for(xb=k-n+1;xb<=n;xb++)
         for(xc=k-n+1;xc<=n;xc++){
             calc1();
             f[k][xa][xb][xc] = t;
            
             calc2();
             f[k][xa][xb][xc] += t;
         }
}
void calc1(){
     t = f[k-1][xa][xb][xc];
     if(t<f[k-1][xa-1][xb][xc]) t=f[k-1][xa-1][xb][xc];
     if(t<f[k-1][xa][xb-1][xc]) t=f[k-1][xa][xb-1][xc];
     if(t<f[k-1][xa][xb][xc-1]) t=f[k-1][xa][xb][xc-1];
     if(t<f[k-1][xa-1][xb-1][xc]) t=f[k-1][xa-1][xb-1][xc];
     if(t<f[k-1][xa-1][xb][xc-1]) t=f[k-1][xa-1][xb][xc-1];
     if(t<f[k-1][xa][xb-1][xc-1]) t=f[k-1][xa][xb-1][xc-1];
     if(t<f[k-1][xa-1][xb-1][xc-1]) t=f[k-1][xa-1][xb-1][xc-1];
}
void calc2(){
     if(xa==xb&&xb==xc) t = value[xa][k-xa+1];
     else if(xa==xb&&xb!=xc) t = value[xa][k-xa+1] + value[xc][k-xc+1];
     else if(xa!=xb&&xb==xc) t = value[xa][k-xa+1] + value[xb][k-xb+1];
     else if(xa!=xb&&xb!=xc&&xa==xc) t = value[xa][k-xa+1] + value[xb][k-xb+1];
     else t = value[xa][k-xa+1] + value[xb][k-xb+1] + value[xc][k-xc+1];
}