给定两个正整数 n,c ,再给定两个长度为 n 的数组 x 与 y ,在满足 a 与 b
都是整数且 a+b=c 的条件下,求使得 \(∑_{i=1}^n(x_i−a)×(y_i−b)\) 最大的 a 和
b
直接化简要求的式子,化成二次函数即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
#include<iostream> usingnamespace std; #define int long long constint N = 1e5 + 10; int x[N], y[N]; signedmain() { int n, c; cin >> n >> c; for (int i = 1; i <= n; i++) cin >> x[i], x[i] += x[i - 1]; for (int i = 1; i <= n; i++) cin >> y[i], y[i] += y[i - 1]; int t = (n * c - y[n] + x[n]) / (2 * n), ans = n * t * (c - t) - t * y[n] - (c - t) * x[n]; if (n * (t + 1) * (c - t - 1) - (t + 1) * y[n] - (c - t - 1) * x[n] > ans) t = t + 1; cout << t << " " << c - t; return0; }
#include<iostream> #include<cstring> usingnamespace std; #define int long long constint N = 350; int f[N][N]; char s[N]; intdfs(int l, int r) { //递归结束条件 if (l == r) return0;//只有一个,不能删除 if (l > r) return1;//删除完成 if (l + 1 == r) return s[l] == s[r];//有两个,判断是否相等 if (~f[l][r]) return f[l][r];//记忆化搜索,如果之前存过,直接用
int t = 0; //判断左右两个子段是否可以删除 for (int i = l ; i < r; i++) { t |= dfs(l, i) && dfs(i + 1, r); } //如果边界相等,判断内部是否可删除 if (s[l] == s[r]) { t |= dfs(l + 1, r - 1); //以i为中心判断回文字符串 for (int i = l + 1; i < r; i++) t |= dfs(l + 1, i - 1) && dfs(i + 1, r - 1); } return f[l][r] = t; } signedmain() { int t; cin >> t; while (t--) { memset(f, -1, sizeof f);//记忆化搜索 int n; cin >> n; for(int i = 1; i <= n; i++) cin >> s[i]; cout << (dfs(1, n) ? "YES" : "NO") << '\n'; } return0; }