首页 > 代码库 > pojj2531

pojj2531

#include<iostream>
using namespace std;
int n;
int map[21][21];
int c1[21],c2[21];
int count1,count2;
int maxsum;

void dfs(int step,int count1, int count2)
{
    if(step==n)
    {
        int sum=0;
        for(int i=0;i<count1;i++)
        {
            for(int j=0;j<count2;j++)
            {
                sum=sum+map[c1[i]][c2[j]];
                if(sum>maxsum)
                    maxsum=sum;
            }
        }
        return;
    }
    int temp1=count1;
    c1[temp1]=step;
    dfs(step+1,count1+1,count2);
    c1[temp1]=0;

    int temp2=count2;
    c2[temp2]=step;
    dfs(step+1,count1,count2+1);
    c2[temp2]=0;
}

int main()
{
    //freopen("input.txt","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>map[i][j];
    for(int i=0;i<n;i++)
    {
        c1[i]=-1;
        c2[i]=-1;
    }
    maxsum=0;
    dfs(0,0, 0);
    cout<<maxsum;
    return 0;
}

 

pojj2531