CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====ABCD=====
  * 题意:大水题

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

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

  * 题解:设$f[i]$为第$i$位为$1$的最少操作数，dp即可，状态转移看代码。<code cpp>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]);
}</code>

=====F=====
  * 题意:给定一个$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)$。

CVBB ACM Team

用户工具

站点工具

页面工具