# AcWing 2. 01背包问题 defmain(): N = 1010 v = [0] * N w = [0] * N f = [[0] * N for _ inrange(N)] # 状态表示，属性为MAX # 隐含了初始化，没有物品的时候，背包的价值永远是0 n, m = map(int, input().split()) for i inrange(1, n + 1): v[i], w[i] = map(int, input().split()) for i inrange(1, n + 1): for j inrange(1, m + 1): # 不选择当前物品，则价值等于前i-1个物品在同容量下的MAX f[i][j] = f[i - 1][j] # 如果j没有v[i]大，则说明装不下第i件物品，那么含i的集合就是空集 # 选择当前物品，前提是j >= v[i]，则价值等于前i-1个物品在同j-v[i]容量下的MAX加上第i个物品价值 if j >= v[i]: f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]) print(f[n][m])
int cnt = 0; for (int i = 1; i <= n; ++ i){ int a, b, s; cin >> a >> b >> s; int k = 1; // 二进制优化，转换为01背包问题 while(k <= s){ cnt ++; v[cnt] = a * k, w[cnt] = b * k; s -= k; k *= 2; } if (s > 0){ cnt ++; v[cnt] = a * s, w[cnt] = b * s; } }
// 边界条件：f[0~cnt] = 0 // 01背包问题 for (int i = 1; i <= cnt; ++ i) for (int j = m; j >= v[i]; -- j) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return0; }
intmain(){ int n; scanf("%d", & n); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++ i){ f[i] = 1; g[i] = 0; for (int j = 1; j < i; ++ j) if (a[j] < a[i]) if (f[i] < f[j] + 1){ f[i] = f[j] + 1; g[i] = j; // 记录状态转移 } }
int k = 1; for (int i = 1; i <= n; ++ i) if (f[k] < f[i]) k = i; printf("%d\n", f[k]);
int s[N], len = f[k]; for (int i = 0; i < len; ++ i){ s[i] = a[k]; k = g[k]; } for (int i = len - 1; i >= 0; -- i) cout << s[i] << " "; cout << endl; return0; }
int n; int a[N]; int q[N]; // q[i]存储当前长度为i的上升字串中的结尾的最小值
intmain(){ scanf("%d", &n); for (int i = 0; i < n; ++ i) scanf("%d", &a[i]); int len = 0; // 记录维护数组q的长度，也是当前最长上升子串长度 // 贪心迭代顺序——按原序遍历串中每个数字 for (int i = 0; i < n; ++ i){ // 二分查找每个候选对象的最优插入位置——插到可以插入的最长子串 // 注意这里l始终初始为0，这样解决了a[i]小于任何长度大于1的子串结尾导致找不到插入位置的问题 // q[0]此时相当于哨兵，a[i]一定大于0，对应于至少可以自己构成一个长度为1的子串 int l = 0, r = len; // 找小于当前数的最大的数 while (l < r){ int mid = l + r + 1 >> 1; if (q[mid] < a[i]) l = mid; else r = mid - 1; } len = max(len, r + 1); // 更新最大长度 q[r + 1] = a[i]; // 更新维护数组 // 注意这里非常巧妙的处理了初始的情况 // 初始时l = r = 0， 直接将a[0]放入长度为1的子串的结尾维护位置中 } printf("%d\n", len); return0; }
intmain(){ int n, m; scanf("%d %d %s %s", &n, &m, a + 1, b + 1); // 易错点：这里数组从第二个位置开始存储
for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j){ f[i][j] = max(f[i-1][j], f[i][j-1]); if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1] + 1); } cout << f[n][m] <<endl; return0; }
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
defmain(): n, m = map(int, input().split()) a = " " + input() b = " " + input() f = [[0] * (m + 1) for _ inrange(n + 1)] # 注意存储从下标1开始 for i inrange(1, n + 1): for j inrange(1, m + 1): f[i][j] = max(f[i-1][j], f[i][j-1]) if a[i] == b[j]: f[i][j] = max(f[i][j], f[i-1][j-1] + 1) print(f[n][m]) if __name__ == "__main__": main()
# AcWing 902. 最短编辑距离 defmain(): n = int(input()) a = " " + input() m = int(input()) b = " " + input() f = [[0] * (m + 1) for _ inrange(n + 1)] for i inrange(n+1): f[i][0] = i for i inrange(m + 1): f[0][i] = i for i inrange(1, n + 1): for j inrange(1, m + 1): f[i][j] = min(f[i-1][j], f[i][j-1]) + 1 if a[i] == b[j]: f[i][j] = min(f[i][j], f[i-1][j-1]) else: f[i][j] = min(f[i][j], f[i-1][j-1] + 1) print(f[n][m]) if __name__ == "__main__": main()
defmain(): n, m = map(int, input().split()) s = [" " + input() for _ inrange(n)] f = [[0] * 1001for _ inrange(1001)] for _ inrange(m): res = 0 b, l = input().split() b = " " + b l = int(l) for a in s: la = len(a) - 1 lb = len(b) - 1 for i inrange(la + 1): f[i][0] = i for i inrange(lb + 1): f[0][i] = i for i inrange(1, la + 1): for j inrange(1, lb + 1): f[i][j] = min(f[i-1][j], f[i][j-1]) + 1 if a[i] == b[j]: f[i][j] = min(f[i][j], f[i-1][j-1]) else: f[i][j] = min(f[i][j], f[i-1][j-1] + 1) if f[la][lb] <= l: res += 1 print(res) if __name__ == "__main__": main()
intmain(){ int n; cin >> n; for (int i = 1; i <= n; ++ i) cin >> s[i]; for (int i = 1; i <= n; ++ i) s[i] += s[i-1];// 求前缀和
// 本题递推中只涉及区间数据的和 // 求任意区间的数据的和可以采用前缀和的方法
// 以区间长度从小到大来枚举所有状态 // 边界条件：区间长度为1，值为0 for (int len = 2; len <= n; len ++) for (int i = 1; i + len - 1 <= n; ++ i){ // i为区间起点 int l = i, r = i + len - 1; // 区间左右端点 f[l][r] = 1e9; // 注意求的是最小值，一定要先把状态值初始化为比较大的值 for (int k = l; k < r; ++ k) // 注意k<r，补去等。 k为子区间的分界点 f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); } cout << f[1][n] <<endl; return0; }
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
defmain(): n = int(input()) s = [0] + list(map(int, input().split())) f = [[float("inf")] * (n + 1) for _ inrange(n + 1)] for i inrange(1, n + 1): f[i][i] = 0 s[i] += s[i - 1] # 前缀和 # 注意这里的遍历范围是极容易错的 forleninrange(2, n + 1): for i inrange(1, n + 1 - len + 1): l, r = i, i + len - 1 for k inrange(l, r): f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l - 1]) print(f[1][n])
// 边界条件: 空集作为一种方案 f[0] = 1; for (int i = 1; i <= n; ++ i) for (int j = i; j <= n; ++ j) f[j] = (f[j] + f[j-i]) % mod;
cout << f[n] << endl; return0; }
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# f[i][j] = f[i-1][j] + f[i-1][j-1*i] + f[i-1][j-2*i] + ... + f[i-1][j-k*i] # f[i][j-i] = f[i-1][j-i] + f[i][j-2*i] + ... + f[i-1][j-k*i] defmain(): n = int(input()) f = [[0] * (n + 1) for _ inrange(n + 1)] mod = int(1e9 + 7) f[0][0] = 1# f[0][0]表示的是从0个数中选体积为0的方案，也就是1个方案 for i inrange(1, n + 1): for j inrange(n + 1): f[i][j] = f[i-1][j] % mod if j >= i: f[i][j] = (f[i][j] + f[i][j-i]) % mod print(f[n][n])
if __name__ == "__main__": main()
1 2 3 4 5 6 7 8 9 10 11 12 13
defmain(): n = int(input()) f = [0] * (n + 1) mod = int(1e9 + 7) f[0] = 1# f[0][0]表示的是从0个数中选体积为0的方案，也就是1个方案 for i inrange(1, n + 1): for j inrange(i, n + 1): f[j] = (f[j] + f[j-i]) % mod print(f[n])
intget(vector<int> num, int l, int r){// 求出从第l位到第r位组成的数的大小 int res = 0; for (int i = l; i >= r; -- i) res = res * 10 + num[i]; return res; }
intpower10(int x){// 求10^x的大小 int res = 1; while(x--) res *= 10; return res; }
intcount(int n, int x){ if (!n) return0;
num.clear(); while(n){ num.push_back(n % 10); //首先将每一位提出来 n /= 10; } n = num.size(); // 保存总位数
int res = 0; // vector从0开始，注意循环的范围 // 注意这里巧妙的写法：i = n - 1 - !x，这样写避免了0作为第一位 // 注意i表示第几位的位数 for (int i = n - 1 - !x; i >= 0; -- i){ if (i < n - 1){ // 作为首位时此情况不存在 res += get(num, n - 1, i + 1) * power10(i); if (!x) res -= power10(i); // x = 0时从001开始 } if (num[i] == x) res += get(num, i - 1, 0) + 1; elseif(num[i] > x) res += power10(i); // 注意i从0开始，所以这里不是i-1 } return res; }
intmain(){
int a, b; while(cin >> a >> b, a || b){ if (a > b) swap(a, b);
for (int i = 0; i <= 9; ++ i) cout << count(b, i) - count(a - 1, i) << ' '; cout << endl; } return0; }
defmain(): # 状态是否有效 ok = [False] * (1 << 12) # 每个状态能被转移过来的状态 state = {}
whileTrue: n, m = map(int, input().split()) M = 1 << n ifnot n: break # 预处理每个状态是否合法（能否竖向插入） for i inrange(M): cnt, valid = 0, True for j inrange(n): if i >> j & 1: if cnt & 1: break cnt = 0 else: cnt += 1 if cnt & 1: valid = False ok[i] = valid # 预处理每个状态的转移子集，求出每个状态后面能接的非法状态 for j inrange(M): state[j] = [] for k inrange(M): # 检查第 i - 2 列与第 i - 1 列是否冲突，二进制 1 表示当前行是牌板尾部 # 即状态前后表示要么是 [尾，头]，要么是 [头，尾] # 此时第 i - 1 列的最终态已确定，检查第 i - 1 列能否满足竖向插入 ifnot (j & k) and ok[j | k]: state[j].append(k) # DP 过程，前 i - 1 列安排完毕，第 i - 1 列能转移到第 i 列的方案数转移 dp = [[0] * M for _ inrange(m + 1)] dp[0][0] = 1 for i inrange(1, m + 1): for j inrange(M): for k in state[j]: dp[i][j] += dp[i - 1][k] # 前 m 列安排完毕，且没有牌板出界的所有方案数 print(dp[m][0])
defmain(): n = int(input()) d = [list(map(int, input().split())) for _ inrange(n)] M = 1 << n f = [[float("inf")] * n for _ inrange(M)] # 起点距离为 0 f[0][0] = 0 for i inrange(M): for j inrange(n): if i >> j & 1: for k inrange(n): if i >> k & 1: # 可到达点 k、j，且当前在点 k 中转到点 j 的最短路径 # f[i -(1 << j)][k]对应于挖去节点j，且最后的节点为k的最优路径值 f[i][j] = min(f[i][j], f[i - (1 << j)][k] + d[k][j]) # 最后是全1的状态，终点为n-1 print(f[M-1][n-1]) if __name__ == "__main__": main()
for (int i = 0; i < n - 1; ++ i) scanf("%d", &happy[i]);
memset(h, -1, sizeof h); for (int i = 0; i < n - 1; ++ i){ int a, b; scanf("%d%d", &a, &b); add(b, a); has_fa[a] = true; } int root = 1; while (has_fa[root]) ++ root;
// 记忆化搜索——在dfs中加入存储 // dp(i, j)返回f[i][j] intdp(int x, int y){ int &v = f[x][y]; if (v != -1) return v; // 说明f[x][y]已经求出来了，直接返回即可 // 避免重复计算；不同于递推，递归中会出现重复问题，要进行标记 // 这里重复是因为我们在main()中会遍历所有f[i][j]，而dp中会进行存储，避免重复计算
v = 1; // 至少为1 for (int i = 0; i < 4; ++ i){ int a = x + dx[i], b = y + dy[i]; if (a >= 1 && a <= n && b >= 1 &&b <= m && h[x][y] > h[a][b])// 注意边界问题 v = max(v, dp(a, b) + 1); // 注意要进行递归， dp[i][j]会返回f[i][j] }
return v; }
intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) scanf("%d", &h[i][j]);
memset(f, -1, sizeof f);// 将所有状态都先初始化为-1，表示每个状态都没有被算过 int res = 0; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) res = max(res, dp(i, j)); printf("%d\n", res); return0; }
defmain(): n, m = map(int, input().split()) h = [[0] * m] + [[0] + list(map(int, input().split())) for _ inrange(n)] f = [[-1] * (m + 1) for _ inrange(n + 1)] d_x = [-1, 0, 1, 0] d_y = [0, 1, 0, -1] defdp(x, y): # f[x][y]已经求出来了，直接返回即可 if f[x][y] != -1: return f[x][y] # 注意初始化，至少为1 f[x][y] = 1 for dx, dy inzip(d_x, d_y): nx, ny = x + dx, y + dy if1 <= nx <= n and1 <= ny <= m and h[nx][ny] < h[x][y]: f[x][y] = max(f[x][y], dp(nx, ny) + 1) return f[x][y] # 遍历每个状态 res = 0 for i inrange(1, n + 1): for j inrange(1, m + 1): res = max(res, dp(i, j)) print(res) if __name__ == "__main__": main()
