洛谷P5322 [BJOI2019] 排兵布阵

本文主要是介绍洛谷P5322 [BJOI2019] 排兵布阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分组背包
题目链接

思路

发现因为策略不变，所以当第$j$个人的第$i$个城堡被攻占时，所有对第$i$个城堡出兵数量小于第$j$个人的都会被攻占
现在我们可以用上面的结论推翻$s$轮对做题的限制，让每个城堡作为一组，每组里有$s$个玩家
为了方便计算增加的分数，我们需要给每个城堡排序

ACcode

#include<bits/stdc++.h>using namespace std;const int M = 2e4 + 9;
int dp[M], a[M][M];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int s, n, m;cin >> s >> n >> m;for (int i = 1;i <= s;i++)for (int j = 1;j <= n;j++)cin >> a[j][i];//第i个玩家的第j个城堡for (int i = 1;i <= n;i++)sort(a[i] + 1, a[i] + 1 + s);for (int i = 1;i <= n;i++)//城堡for (int j = m;j >= 0;j--)for (int k = 1;k <= s;k++)//每个玩家if (j > a[i][k] * 2)dp[j] = max(dp[j], dp[j - a[i][k] * 2 - 1] + i * k);int ans = 0;for (int i = 0;i <= m;i++)ans = max(ans, dp[i]);cout << ans;return 0;
}

这篇关于洛谷P5322 [BJOI2019] 排兵布阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---