2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3 [2020/05/15 20:57] jjleo 创建 |
2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3 [2020/05/15 22:36] (当前版本) jjleo [F] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| =====E===== | =====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===== | =====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)$。 |
2020-2021/teams/farmer_john/jjleo/codeforces_round_642_div._3.1589547455.txt.gz · 最后更改: 2020/05/15 20:57 由 jjleo
