賽后總結：第一次距離金這么近，而且這道題幾乎同型別的題，某acw網站演算法基礎課的 最短Hamilton路徑，我還做過，但是當時沒有想到兩者一些相同的性質，還是練的少，明年省賽繼續努力吧，
光棍節即將來臨，小辣參加了某資本家的某游戲
即四根光棍在如圖場景進行游戲，每個格子有一個數值 你可以擲若干次骰子，每次隨機擲出 1 ~ 6 之間的整數值，加入糖果庫存
如果某次擲骰子后你的糖果庫存大于某個格子的數值，且這個格子與你占領的格子相鄰，那么你可以選擇占領這個格子，占領后庫存清 0
我們稱兩個格子相鄰當且僅當有一條邊重合 默認一開始你位于左下方(即圖中顯示“我方”的位置)，也就是說只有左下方的格子與你相鄰
小辣用二十年單身換取了 n 次擲骰子的機會，你能告訴他最好情況下最多能占領幾個格子嗎
輸入
第一行一個整數 T, 表示資料組數，對于每組資料：
第一行 17 個正整數，依次表示圖中從左到右從上到下17個格子的數值，前四個表示第一行四個格子，第五到七表示第二行三個，以此類推，
第二行 1 個非負整數 n，表示擲骰子的次數
1≤T≤20, 保證所有資料 ≤109
輸出
對于每組樣例輸出一行一個整數，表示最多能占領的格子數量
樣例輸入 Copy
2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
100
樣例輸出 Copy
10
17
簡單解題代碼＋思路注釋
#include <bits/stdc++.h>
using namespace std;
int t,ar[20],sum,ans,cnt;
bool st[6][6]; /// 建圖需要的陣列
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; /// 搜索上下左右四個方向
void init(int x) /// 建圖
{
if(x==1) st[5][1] = true;
else if(x==2) st[5][2] = true;
else if(x==3) st[5][4] = true;
else if(x==4) st[5][5] = true;
else if(x==5) st[4][2] = true;
else if(x==6) st[4][3] = true;
else if(x==7) st[4][4] = true;
else if(x==8) st[3][2] = true;
else if(x==9) st[3][3] = true;
else if(x==10) st[3][4] = true;
else if(x==11) st[2][2] = true;
else if(x==12) st[2][3] = true;
else if(x==13) st[2][4] = true;
else if(x==14) st[1][1] = true;
else if(x==15) st[1][2] = true;
else if(x==16) st[1][4] = true;
else if(x==17) st[1][5] = true;
}
void dfs(int x,int y) /// 只搜一遍獲取最大連通塊數量
{
st[x][y] = false; cnt++;
for(int i=0; i<4; i++)
{
int dx_1 = x+dx[i],dy_1 = y+dy[i];
if(dx_1<1||dx_1>5||dy_1<1||dy_1>5||!st[dx_1][dy_1]) continue;
dfs(dx_1,dy_1);
}
}
int main()
{
cin>>t;
while(t--)
{
ans = 0; /// 記錄能達到的最多的點
for(int i=1; i<=17; i++) cin>>ar[i]; /// 存下每個方格需要的糖果數量
cin>>sum; /// 篩子個數
for(int i=0; i< 1<<17; i++) /// 把所有情況不重復遍歷一遍
{
memset(st, 0, sizeof st); /// 每次使用方法都要把陣列重置一下
int res = 0,sum1=0; /// sum1記錄每一種方法所使用的糖果數
for(int j=0; j<17; j++) /// 一共17個點所以要進行
{
if(i>>j&1)
{
res++;
init(j+1);
if(ar[j+1]%6!=0) sum1+=(ar[j+1]/6+1); ///每次使用篩子的判定
else sum1+=(ar[j+1]/6);
}
}
if(sum<sum1) continue;
cnt = 0;
if(!st[1][1]) continue; /// 起始點不存在的情況
dfs(1,1); /// 判斷選中的幾個點能否連通成一個連通塊
if(res == cnt) ans = max(ans,res);
}
cout<<ans<<"\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348507.html
標籤：其他
上一篇：【小心】系列
下一篇：爬蟲-自動化完成上百題目