本文主要是介绍The 2024 International Collegiate Programming Contest in Hubei Province, China，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
H. Genshin Impact Startup Forbidden III
估计还会补D，I，K
H. Genshin Impact Startup Forbidden III
对于一个有鱼的池塘，有周围与自己本身五个关键位置可以捕获当前位位置的鱼。把这些位置存储到 map中。用四进制数 S 表示每块池塘中剩余的鱼的数目，dp[S] 表示达成该状态最少的炸弹数。枚举所有的关键位置，计算状态的转移。
#define PII pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 1e9 + 7;
map < PII, vector<int>>mp;
PII pos[5] = { {0,0},{0,1},{1,0},{-1,0},{0,-1} };
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);vector<int>pow(15);pow[0] = 1;for (int i = 1; i < 11; i++) {pow[i] = pow[i - 1] * 4;}int n, m, k;cin >> n >> m >> k;vector<int>val;int res = 0;for (int I = 0; I < k; I++){int x, y, a;cin >> x >> y >> a;val.push_back(a);res += int(a*pow[I]);for (int i = 0; i < 5; i++){int xx = x + pos[i].first, yy = y + pos[i].second;if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue;mp[{xx, yy}].push_back(I);}}auto check = [&](int x){for (int i = 0; i < k; i++) {if (x % 4 > val[i]) return true;x /= 4;}return false;};auto check2 = [&](int x, int y){for (int i = 0; i < y; i++) {x /= 4;}if (x % 4 == val[y]) return true;return false;};vector<int>dp(int(pow[ k]),inf);dp[0] = 0;for (int i = 0; i<int(pow[k]); i++) {if (check(i)) continue;for (auto w : mp) {vector<int>& tmp = w.second;int t = i;for (auto ww : tmp) {if (check2(t,ww)) continue;t += int(pow[ww]);}dp[t] = min(dp[t], dp[i] + 1);}}cout << dp[res];
}这篇关于The 2024 International Collegiate Programming Contest in Hubei Province, China的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
