题目链接：https://codeforces.com/contest/1353
题目大意：
给你一个长度为 n 的 01 字符串和一个整数 k，每次操作你可以选择一个字符并改变其状态，要使字符串中相邻 1 的距离为 k，问最少需要操作几次。
想法：
我们设 dp[i][0/1]
dp[i][0] 代表第 i 项是 0 的合法序列的最小修改次数
dp[i][1] 代表第 i 项是 1 的合法序列的最小修改次数
明显dp[i][0] 转移的方程： 要么前面一项是 1 合法 或者 前面一项是 0 合法，min(dp[i-1][0],dp[i-1][1])
明显dp[i][1] 转移的方程： 要么前面 i-1 项全部是0，或者 i - k 项是合法的结尾是 1 的序列并且 i - k + 1 ~ i - 1 都是 0 ，min(sum[i-1],dp[p][1]+sum[i-1]-sum[p])
采用前缀和预处理一下 1 的个数。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <algorithm> #include <string> #include <cstring> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <iomanip> #include <ctime> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define ll long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f3f3f3f3f #define max(a, b) (a>b?a:b) #define min(a, b) (a<b?a:b) const double eps = 1e-10; const int maxn = 1e6 + 10; const int MOD = 998244353; int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; } using namespace std; char s[maxn]; int dp[maxn][2],sum[maxn]; int main() { int t; scanf("%d",&t); while (t--) { int n,k; scanf("%d%d",&n,&k); scanf("%s",s+1); dp[0][0] = dp[0][1] = 0; for (int i = 1;i <= n;i++) { sum[i] = sum[i - 1] + (s[i] == '1'); dp[i][0] = dp[i][1] = 0; } for (int i = 1;i <= n;i++) { int p = max(0,i-k); dp[i][0] = min(dp[i-1][1],dp[i-1][0]) + (s[i] == '1'); dp[i][1] = min(sum[i-1],dp[p][1]+sum[i-1]-sum[p]) + (s[i] == '0'); } printf("%d ",min(dp[n][0],dp[n][1])); } return 0; }
题目链接：https://codeforces.com/contest/1353
题目大意：
想法：
考虑如果不做操作，就是一道很经典的dp，所以现在需要确定的是，操作结束之后的矩阵。
首先一定会有一个格子的高度保持不变
由起点的高度可以推得所有格子的高度
所以我们枚举高度不变的格子，依据他计算出起点高度，之后枚举起点高度即可
设 f[i][j] 代表从 f[0][0] 到 （i，j） 所需要的修改的最小次数
转移方程的化和数塔问题是一样的 if (j >= 1) f[i][j] = min(f[i][j],f[i][j-1]); f (i >= 1) f[i][j] = min(f[i][j],f[i-1][j]);
枚举起点的复杂度是O（n^2），dp 的复杂度是 O（n^2）, 总的复杂是 O(n^4)
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <algorithm> #include <string> #include <cstring> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <iomanip> #include <ctime> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define ll long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f3f3f3f3f #define max(a, b) (a>b?a:b) #define min(a, b) (a<b?a:b) const double eps = 1e-10; const int maxn = 100 + 10; const int MOD = 998244353; int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; } using namespace std; ll f[maxn][maxn],a[maxn][maxn]; ll t,n,m; ll solve(ll h) { for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) f[i][j] = INF; } f[0][0] = 0; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { ll v = i + j + h; if (a[i][j] < v) { f[i][j] = INF; continue; } if (j >= 1) f[i][j] = min(f[i][j],f[i][j-1]); if (i >= 1) f[i][j] = min(f[i][j],f[i-1][j]); f[i][j] += a[i][j] - v; } } return f[n-1][m-1]; } int main() { ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n >> m; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) cin >> a[i][j]; } ll ans = INF; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { ans = min(ans,solve(a[i][j]-i-j)); } } cout << ans << endl; } return 0; }