gobang.cpp

第四届百度杯编程大赛final解题报告+标程

/**********************************************************************
Author: Sherlock
Created Time:  2009-02-18 20:12:29
File Name: 
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

const int   maxSize     =   15;
const int   maxcredit    =   12 * 10 + 10;

int         n;
int         exp[maxSize][maxSize], credit[maxSize][maxSize], a[maxSize], pows[maxSize], f[maxcredit][1 << 15];

void            init_power()
{
    pows[0] = 1;
    for (int i = 1; i < 15; i ++)
        pows[i] = pows[i - 1] * 2;
}

void            init()
{
    for (int i = 0; i < n; i ++)  
        for (int j = 0; j < n; j ++)
            scanf("%d", &exp[i][j]);
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            scanf("%d", &credit[i][j]);
    for (int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
}

void            solve()
{
    if (n == 1)
    {
        printf("0\n");
        return ;
    }
    
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    for (int p = 0; p < pows[n - 1]; p ++)
    {
        int sum = 0;
        for (int i = 1; i < n; i ++)
            if ((p & pows[i - 1]) != 0)
                sum += credit[0][i];
        for (int i = 0; i <= sum; i ++)
            if (f[i][p] >= 0)
            {
                for (int j = 1; j < n; j ++)
                    if ((p & pows[j - 1]) == 0)
                    {
                        if (a[0] + f[i][p] > a[j])
                            f[i + credit[0][j]][p + pows[j - 1]] = max(f[i + credit[0][j]][p + pows[j - 1]], f[i][p] + exp[0][j]);
                        else
                            f[i][p + pows[j - 1]] = max(f[i][p + pows[j - 1]], f[i][p] + exp[0][j]);
                    }
            }
    }
    
    int sum = 0;
    for (int i = 1; i < n; i ++)
        sum += credit[0][i];
    for (int i = sum; i >= 0; i --)
        if (f[i][pows[n - 1] - 1] != -1)
        {
            printf("%d\n", i);
            break;
        }
}

int             main()
{
    int test_num;
    scanf("%d", &test_num);
    init_power();
    while (test_num > 0)
    {
        test_num --;
        scanf("%d", &n);
        init();
        solve();
    }
    return 0;
}