方格取数
题目描述：给你一个m行n列的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，并且取出的数的和最大。
输入：多组测试数据，第一行有两个整数m和n(m,n<=50)，接下来是m*n个非负数，
输出：对于每组数据计算出最大和并输出。
样例输入：3 375 15 21 75 15 28 34 70 5
样例输出：188
//============================================================================ // Name : 方格取数.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> using namespace std; int n; int a[10][10]; int f[10][10][10][10]; void compute_f() { int i1,i2,j1,j2; for(i1=0;i1<=n;i1++) { for(j1=0;j1<=n;j1++) { for(i2=0;i2<=n;i2++) { for(j2=0;j2<=n;j2++) { f[i1][j1][i2][j2]=0; } } } } for(i1=1;i1<=n;i1++) { for(j1=1;j1<=n;j1++) { for(i2=1;i2<=n;i2++) { for(j2=1;j2<=n;j2++) { if(f[i1][j1][i2][j2]<f[i1-1][j1][i2-1][j2]) f[i1][j1][i2][j2]=f[i1-1][j1][i2-1][j2]; if(f[i1][j1][i2][j2]<f[i1-1][j1][i2][j2-1]) f[i1][j1][i2][j2]=f[i1-1][j1][i2][j2-1]; if(f[i1][j1][i2][j2]<f[i1][j1-1][i2-1][j2]) f[i1][j1][i2][j2]=f[i1][j1-1][i2-1][j2]; if(f[i1][j1][i2][j2]<f[i1][j1-1][i2][j2-1]) f[i1][j1][i2][j2]=f[i1][j1-1][i2][j2-1]; if(i1==i2&&j1==j2) { f[i1][j1][i2][j2]=f[i1][j1][i2][j2]+a[i1][j1]; } else { f[i1][j1][i2][j2]=f[i1][j1][i2][j2]+a[i1][j1]+a[i2][j2]; } cout<<"f["<<i1<<"]["<<j1<<"]["<<i2<<"]["<<j2<<"]="<<f[i1][j1][i2][j2]<<endl; } } } } } int main() { n=8; a[2][3]=13; a[2][6]=6; a[3][5]=7; a[4][4]=14; a[5][2]=21; a[5][6]=4; a[6][3]=15; a[7][2]=14; compute_f(); cout<<f[8][8][8][8]; return 0; }
