layui做移动网站,网站建设内页,哈尔滨制作网站的公司,住房与建设注册中心网站题意
传送门 Codeforces 1579G Minimal Coverage
题解
DP d p [ i 1 ] [ j ] dp[i1][j] dp[i1][j] 代表 0 ⋯ i 0\cdots i 0⋯i 次移动后所在位置与覆盖区域最左侧位置相差 j j j 时#xff0c;覆盖区域的最小值。枚举左右方向递推即可。总时间复杂度 O ( n ⋅ max …题意
传送门 Codeforces 1579G Minimal Coverage
题解
DP d p [ i 1 ] [ j ] dp[i1][j] dp[i1][j] 代表 0 ⋯ i 0\cdots i 0⋯i 次移动后所在位置与覆盖区域最左侧位置相差 j j j 时覆盖区域的最小值。枚举左右方向递推即可。总时间复杂度 O ( n ⋅ max { a i } ) O(n\cdot\max\{a_i\}) O(n⋅max{ai})。
#include bits/stdc.h
using namespace std;
constexpr int M 2E3, INF 1e9;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt;cin tt;while (tt--) {int n;cin n;vectorint a(n);for (int i 0; i n; i) {cin a[i];}auto _min [](int x, int y) {x min(x, y);};vectorvectorint dp(n 1, vectorint(M, INF));dp[0][0] 0;for (int i 0; i n; i) {for (int j 0; j M; j) {if (dp[i][j] INF) {continue;}if (j a[i] M) {_min(dp[i 1][j a[i]], max(dp[i][j], j a[i]));}if (j - a[i] 0) {_min(dp[i 1][j - a[i]], dp[i][j]);} else {_min(dp[i 1][0], dp[i][j] a[i] - j);}}}int res *min_element(dp[n].begin(), dp[n].end());cout res \n;}return 0;
}二分 bitset
二分覆盖区域的大小 d d d。用 std::bitset 维护当前的可能位置初始位置可能位于 [ 0 , d ) [0,d) [0,d) 中的任一个位置递推即可。总时间复杂度 O ( n ⋅ max { a i } ⋅ log n / 32 ) O(n\cdot\max\{a_i\}\cdot\log n/32) O(n⋅max{ai}⋅logn/32)。
#include bits/stdc.h
using namespace std;
constexpr int N 2E3;
using bt bitsetN;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt;cin tt;while (tt--) {int n;cin n;vectorint a(n);for (int i 0; i n; i) {cin a[i];}auto judge [](int d) {bt x, mask;for (int i 0; i d; i) {x[i] mask[i] 1;}for (int i 0; i n; i) {x ((x a[i]) | (x a[i])) mask;}return x.any();};int lb 0, ub N;while (ub - lb 1) {int mid (lb ub) / 2;if (judge(mid)) {ub mid;} else {lb mid;}}cout ub - 1 \n;}return 0;
}
