submarine_sherlock.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/**********************************************************************
Author: Sherlock
Created Time:  2009-02-21 10:57:23
File Name: 
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

const int   maxSize     =   30 + 2;
const int   maxSizeW    =   10 + 1;
const int   maxSizeP    =   600;
const int   speed       =   2;

int         n, d, w, T;
int         pows[10], f[maxSize][maxSizeW][maxSizeP][2], g[3];
bool        done[maxSize][maxSizeW][maxSizeP][2];

struct      que_type
{
    int     w, c, d, t;
}   que[maxSize];

void            init()
{
    pows[0] = 1;
    for (int i = 1; i <= w * d; i ++)
        pows[i] = pows[i - 1] * 2;
    for (int i = 0; i < n; i ++)
    {
        scanf("%d%d%d%d", &que[i].w, &que[i].t, &que[i].d, &que[i].c);
        que[i].d --;
    }
}

void            solve()
{
    memset(done, false, sizeof(done));
    f[0][0][0][0] = 0;
    done[0][0][0][0] = true;
    int ans = 0;
    for (int t = 0; t <= T; t ++)
    {
        for (int i = 0; i < w; i ++)
            for (int p = 0; p < pows[w * d]; p ++)
                for (int s = 0; s < 2; s ++)
                    if (done[t][i][p][s])
                    {
                        ans = max(ans, f[t][i][p][s]);
                        int pp = 0;
                        for (int j = 0; j < d; j ++)
                            g[j] = -1;
                        int ttt = 0;
                        for (int j = 0; j < n; j ++)
                        {
                            int op = (t - que[j].t) / speed;
                            if (op >= 0 && op < w && (pows[que[j].d * w + op] & p) > 0 && que[j].t <= t)
                            {
                                if ((t + 1) % speed == que[j].t % speed)
                                {
                                    if (op + 1 < w)
                                        pp += pows[que[j].d * w + op + 1];
                                    if (op + 1 == i)
                                        g[que[j].d] = j;
                                }
                                else
                                {
                                    pp += pows[que[j].d * w + op];
                                    if (op == i)
                                        g[que[j].d] = j;
                                }
                                ttt = 1;
                            }
                            else
                                if (que[j].t == t + 1)
                                {
                                    if (i == 0)
                                        g[que[j].d] = j;
                                    pp += pows[que[j].d * w];
                                }
                        }

                        int op = 1;
                        if (s == 1)
                            op = -1;
                        op = min(max(0, op + i), w - 1);
                        if (! done[t + 1][op][pp][s])
                        {
                            f[t + 1][op][pp][s] = f[t][i][p][s];
                            done[t + 1][op][pp][s] = true;
                        }
                        else
                            f[t + 1][op][pp][s] = max(f[t + 1][op][pp][s], f[t][i][p][s]);
                        if (! done[t + 1][i][pp][s])
                        {
                            f[t + 1][i][pp][s] = f[t][i][p][s];
                            done[t + 1][i][pp][s] = true;
                        }
                        else
                            f[t + 1][i][pp][s] = max(f[t + 1][i][pp][s], f[t][i][p][s]);

                        for (int j = 0; j < d; j ++)
                            if (g[j] != -1)
                            {
                                pp -= pows[j * w + i];
                                int ss = s;
                                if (que[g[j]].c == 1)
                                    ss = 1 - s;
                                if (! done[t + 1][i][pp][ss])
                                {
                                    f[t + 1][i][pp][ss] = f[t][i][p][s] + que[g[j]].w;
                                    done[t + 1][i][pp][ss] = true;
                                }
                                else
                                    f[t + 1][i][pp][ss] = max(f[t + 1][i][pp][ss], f[t][i][p][s] + que[g[j]].w);
                                break;
                            }
                    }
    }

    printf("%d\n", ans);
}

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