120563F

https://ac.nowcoder.com/acm/contest/120563/F

最优结构是：

####P00R#####......

00R######P00R......

原因：

肯定希望第一个尽量右边。

第一个：如果右边一格，那么就可以放在阻挡，对不优；如果左边一格，那么放在，同样对不优。那么这就是能把挡在最右边的结果了。把看成新的起点即可。那么就循环往复了。答案：

#include<bits/stdc++.h>
using namespace std;
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void work(){
	int n=read();
	printf("%d\n",n-1+(n/5));
}
int main(){
	int t=read();
	while(t--){
		work();
	}
	return 0;
}