#include<bits/stdc++.h> using namespace std; typedef long long ll; constexpr int N = 2e5+10; constexpr ll INF = 1e18; int tid, T; ll n, m, k; char c[N]; ll dp[205][N]; //dp[i][j] 操作i次,到位置j时,路径上最少需要的1的数量(落脚点) void solve() { ll cnt1 = 0; cin >> n >> m >> k; for(int i = 0; i <= k; ++i) { for(int j = 0; j <= n; ++j) dp[i][j] = INF; } for(int i = 1; i <= n; ++i) { cin >> c[i]; if(c[i] == '1') cnt1++; } dp[0][0] = 0; for(int i = 0; i <= k; ++i) { //存储位置的索引j,保证队列中dp[i][j]和dp[i-1][j]单调递增 deque<ll> dq0, dq1; dq0.push_back(0); if(i > 0) dq1.push_back(0); for(int j = 1; j <= n; ++j) { //移除[j-m, j-1]范围外的值 while(!dq0.empty() && dq0.front() < j-m) dq0.pop_front(); while(!dq1.empty() && dq1.front() < j-m) dq1.pop_front(); if(!dq0.empty() && c[j] == '1') { dp[i][j] = min(dp[i][j], dp[i][dq0.front()] + 1); } if(!dq1.empty() && c[j] == '0' && i > 0) { dp[i][j] = min(dp[i][j], dp[i-1][dq1.front()] + 1); } //维护队列单调性,加入新元素前,弹出>=的元素 while(!dq0.empty() && dp[i][dq0.back()] >= dp[i][j]) { dq0.pop_back(); } dq0.push_back(j); if(i > 0) { while(!dq1.empty() && dp[i-1][dq1.back()] >= dp[i-1][j]) { dq1.pop_back(); } dq1.push_back(j); } } } bool flag = false; for(int i = 0; i <= k; ++i) { for(int j = n-m+1; j <= n; ++j) { if(dp[i][j] <= cnt1) { flag = true; break; } } } if(n+1 <= m) flag = true; cout << (flag ? "Yes\n" : "No\n"); } int main() { freopen("encore.in", "r", stdin); freopen("encore.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cin >> tid >> T; while(T--) { solve(); } return 0; }
Note.ms
/nyxm