CVBB ACM Team

题意:大水题

题解:练习英语阅读和手速。

题意:给定一个长度为$n$的$01$串，每次操作可以更改某一位，要求使得所有相邻的$1$的间隔为$k$，求最少操作数。$(1 \le n \le 10^6; 1 \le k \le n)$

题解:设$f[i]$为第$i$位为$1$的最少操作数，dp即可，状态转移看代码。

ans = n;
for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + (s[i] == '1');
if(!sum[n]) ans = 0;
for(int i = 1;i <= n;i++){
	f[i] = n;
	if(i - k >= 1) f[i] = min(f[i], f[i - k] + sum[i - 1] - sum[i - k]);
	f[i] = min(f[i], sum[i - 1]);
	f[i] += s[i] == '0';
	ans = min(ans, f[i] + sum[n] - sum[i]);
}

题意:给定一个$n \times m$的方格，每个格子有一个高度$a_{i,j}$，每次操作可以使得某个格子的高度减少$1$，高度可以减少到$0$或负数，要求存在一条路径从左上角到右下角，每次只能往下走或往右走，且只能往当前格子高度大$1$的格子移动，求最少操作次数。$(1 \le n, m \le 100, 1 \le a_{i, j} \le 10^{15})$

题解:当左上角格子的高度确定后就可以直接dp判断是否有解和最小值，但$a_{i, j}$太大不能一个个枚举，注意到左上角格子之所以减少肯定是因为想到达某个格子，但是自己太高了以至于到那个格子后比那个格子的高度还高，所以最优取值一定是要么不减少、要么减少到可以恰好到某个格子的值，即$(a_{i,j}-i-j-2)$，因此暴力枚举然后分别dp即可，复杂度为$O(n^4)$。