寒假训练营1-C题题解

场上这题我其实没做啊，因为看那个通过数量低得可怜，题都没点开，全场在调F和H。结束之后看的C题，问就是非常后悔，血亏！血亏啊！！这题，好简单啊！（不是）

完全怀疑大家被题面劝退了，我看见这个题面我就想跑路 太长了。于是我直接读的输入描述和样例。好 这不就简单了吗 题面害人.jpg

题意简述：给n个语句 每个语句可能会和其前1-3个语句冲突 冲突语句之间至少间隔三个空位。输入n，然后输入n行，每行三个数字。第i行表示第i个语句的冲突情况。第i行的第j个数字表示i语句是否与i-j语句冲突。1为冲突，0为不冲突。可以在任何语句之间插入空语句，问要插入多少个空语句能满足冲突语句之间都间隔至少三个空位。

n最多只有100，那么我们开一个数组a【105】，记录每个语句在满足条件的情况下存放的位置，最后读取a【n】的位置，和不放任何空语句的状态——a【n】=n来比较差值，就是插入的空语句的数量。

显然每个语句放的位置只受前面语句的位置和是否冲突影响，所以可以在读入的时候直接进行处理。拿到一个语句，我们先把它放在上一个语句的后面：a【i】=a【i-1】+1，然后读入，看它和哪个语句存在冲突。如果和i-j的语句冲突，就把它移动一下，也就是a【i】至少要为a【i-j】+4。与多个语句存在冲突，取距离最远的以向下兼容。注意，间隔三个空位是+4，毕竟没间隔就是+1了。

代码：

using namespace std;
int main(){
	int a[105];
	int n;
	int ans=0;
	cin>>n;
	a[0]=0;
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+1;
		for(int j=1;j<=3;j++){
			int now;
			cin>>now;
			if(now==1){
				a[i]=max(a[i-j]+4,a[i]);
			}
		}
	}
	cout<<a[n]-n;
	return 0;
}

顺便一提，其实按这输入顺序，先读入的是更靠近的语句，后读入的一定不会比先读入的大，所以这个max显得没什么毛用（不是）不过左右都是要输入的，这样写起来还更好看（？）