洛谷链接

一群二元x，y取1。但是取法有限制，通用贪心：对y-x排序；取大正差和小负差，因为一定至少会拿所有的min（x，y），接下来就是边界处理，分单人组和多人组，但是当多人组只有一个人的时候变成了单人组

mex题：一般mex都是不大的；可考虑遍历验证；此题采用二分；首先满足mex（x），小于x必须都出现；对于网格图dp走向（向下和右），考虑反例：小于x的元素不是dp走向；

逆向思维+单调队列优化dp

//要求区间全覆盖，并且花费最少，采用dp；dp【i】表示取a【i】且前面满足条件的代价
//很牛的一个思路，不想去想怎么覆盖，而是想上面情况不会覆盖。dpj-->dpi的时候，过程中没有一段///完整的区间！！！orz
//使用优先队列对右端点进行排序，预处理对于每个i取最远的区间左端点；
priority_queue<no> q;
    for (int i = 1, j = 1, k = 0; i <= n; i++) {
        while (j <= m && adj[j].r < i) {
            q.push({adj[j].l, adj[j].r});
            j++;
        }
        if (!q.empty() && q.top().l > k) {
            k = q.top().l;
        }
        p[i] = k;
    }
//单调队列维护p【i】~i的最小dpj
//
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 6e5 + 10;

struct no {
    int l, r;
    bool operator<(const no& A) const {
        if (r == A.r) return l < A.l;
        return r < A.r;
    }
};

int a[N], p[N];
int dp[N], dq[N];
int hh, tt;

void solve() {
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[++n] = 0; // 在数组末尾添加一个0
    cin>>m;
    vector<no> adj(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> adj[i].l >> adj[i].r;
    }
    sort(adj.begin() + 1, adj.end());

    priority_queue<no> q;
    for (int i = 1, j = 1, k = 0; i <= n; i++) {
        while (j <= m && adj[j].r < i) {
            q.push({adj[j].l, adj[j].r});
            j++;
        }
        if (!q.empty() && q.top().l > k) {
            k = q.top().l;
        }
        p[i] = k;
    }

    hh = 0, tt = 0;
    dq[0] = 0;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh <= tt && dq[hh] < p[i]) {
            hh++;
        }
        dp[i] = dp[dq[hh]] + a[i];
        while (hh <= tt && dp[dq[tt]] >= dp[i]) {
            tt--;
        }
        dq[++tt] = i;
    }

    cout << dp[n] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}

时间复杂度分析+牛逼的状态暴力

//样例*状态数（4*k*4*（k-1）...）*每个棋盘遍历（n*m）。
随后进行回溯暴力
#include <bits/stdc++.h>
using namespace std;
#define int long long
int g[7][7];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,k;
int mmax;
void dfs(int cnt){
    mmax=min(mmax,cnt);
    if(mmax==1) return ;
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    if(g[i][j]){
    for(int k=0;k<4;k++){
    int nx=dx[k]+i,ny=dy[k]+j;
    if(nx<1||ny<1||nx>n||ny>m) continue;
    if(!g[nx][ny]) continue;
    int nnx=nx+dx[k],nny=ny+dy[k];
    if(nnx<1||nny<1||nnx>n||nny>m) continue;
    if(g[nnx][nny]) continue;
    g[i][j]=0;
    g[nx][ny]=0;
    g[nnx][nny]=1;
    dfs(cnt-1);
    g[i][j]=1;
    g[nx][ny]=1;
    g[nnx][nny]=0;
    }}
    }
    }
}
void solve() {
    cin>>n>>m>>k;
    memset(g,0,sizeof g);
    int x,y;
    for(int i=0;i<k;i++){
    cin>>x>>y;
    g[x][y]=1;
    }
    mmax=k;
    dfs(k);
    cout<<mmax<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

}