• [ ] 每个男生都会尽量选择远离其他男生的位置，前两个男生一定会选择第一个和最后一个坑位，从第3个男生开始，问题就变为了选择两个男生之间尽量靠中间的的坑位，由于每次选择靠中间的坑位之后，会产生两个新区间，即左边男生到这个男生的区间，这个男生到右边男生的区间，所以我们可以利用分治的思想递归解决；

定义dp[i]为尽可能选择中间位置所能容纳男生的数量；(i>=3，最中间选择之后他左右两边的都不能选) 分两种情况讨论：

1：当i为奇数： dp[i]=dp[(i-3)/2]*2+1(选择中间位置，左右两个位置不能选，减去3） 2： 当i为偶数： {一个区域长度为(i-3)/2,另一个为(i-3)/2+1} dp[i]=dp[(i-3)/2]+dp[(i-3)/2+1]+1; 初始化：(尽可能选择中间的坑位,dp[3]应为1） dp[0]=0; dp[1]=1; dp[2]=1; 递推即得答案

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    int T,n;cin>>T;
    vector<int>dp(350001);
    //初始化 
    dp[0]=0;dp[1]=1;dp[2]=1;
    for(int i=3;i<=350001;i++){
        if(i%2==1)//奇数情况 
        dp[i]=dp[(i-3)/2]*2+1;
        else//偶数情况 
        dp[i]=dp[(i-3)/2]+dp[(i-3)/2+1]+1;
    }   
    for(int i=0;i<T;i++){
        cin>>n;
        //输出的要加上刚开始两个男生，对应坑位减4 
        if(n>=4)cout<<dp[n-4]+2<<'\n';
        else if(n==3)cout<<2<<'\n';
        else cout<<1<<'\n';
    }
	return 0;
}