一. 题目

二. 理论

• 将每个格子映射成二进制上从0~16, 每个格子选和不选一个2^17种情况。

• 二进制枚举所有格子是否选

• 每个格子花费可以提前预处理出来, 贪心每次投6, x/6+1就是花费

三. 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=20;

int T;
int n;
int A[N];//存储占领当前格子需要多少花费
//r存储格子横坐标
//l存储格子纵坐标
int r[N]={0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4};
int c[N]={0, 1, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 0, 1, 3, 4};
int id[N][N];//存储某个格子对应编号

class BinarySearch
{
public://下标偏移量
    int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
    int state, cost;//存储搜索到的状态, 存储当前花费
public:
    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    BinarySearch()
    {
        initIO();
        //预处理一下id数组
        fill(id[0], id[0]+N*N, -1);//id[0]是二维数组的首元素地址
        for(int i=0;i<17;i++)
            id[r[i]][c[i]]=i;
    }

    //起始位置，搜到的状态
    void dfs(int x, int y, int st)//st存的是当前的方案
    {
        if(cost>n) return;//花费超出

        for(int i=0;i<4;i++)
        {
            int a=x+dx[i], b=y+dy[i], t=id[a][b];//无越界, 是合法点, 是二进制中的点, 没被搜过
            if(a<0||a>4||b<0||b>4||t==-1||!(st>>t&1)||state>>t&1) continue;
            state|=1<<t, cost+=A[t], dfs(a, b, st);
        }
    }
}bs;

int main()
{
    cin>>T;
    while(T--)
    {
        for(int i=0;i<17;i++)//计算每个格子花费次数
        {
            cin>>A[i];
            A[i]=A[i]/6+1;
        }

        int ans=0;
        cin>>n;
        for(int i=0;i<1<<17;i++)
            if(i>>13&1)//若起点选了
            {
                bs.state=1<<13, bs.cost=A[13];
                bs.dfs(4, 0, i);//搜

                if(bs.cost<=n&&bs.state==i)//若花费<=n, 并且状态全部搜到
                {
                    int cnt=0;
                    for(int j=0;j<17;j++)
                        if(i>>j&1)
                            cnt++;
                    ans=max(ans, cnt);
                }
            }
        cout<<ans<<endl;
    }
}