lydrainbowcat

1.0万

#include<bits/stdc++.h>
using namespace std;
int f[205][205][205]; // f[l][r][cnt]: l~r合并，其中剩下cnt个与a[l],a[r]同色的最后一起合并
int T, n, m, a[205], b[205]; // a: 颜色，b: 数量
int main() {
cin >> T;
for (int C = 1; C <= T; C++) {
cin >> n;
m = 0;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
if (x == a[m]) b[m]++; else a[++m] = x, b[m] = 1; // 合并连续同色块
}
memset(f, 0xcc, sizeof(f));
for (int i = 1; i <= m; i++)
f[i][i][0] = b[i] * b[i], f[i][i][b[i]] = 0;
for (int len = 2; len <= m; len++)
for (int l = 1; l <= m - len + 1; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++)
f[l][r][0] = max(f[l][r][0], f[l][k][0] + f[k + 1][r][0]);
if (a[l] != a[r]) continue;
int tot = b[l] + b[r]; // 控制一下循环上界，减小常数，避免超时
for (int k = l + 1; k < r; k++)
if (a[k] == a[l]) tot += b[k];
for (int cnt = b[l] + b[r]; cnt <= tot; cnt++) {
for (int k = l + 1; k <= r; k++)
if (a[l] == a[k])
f[l][r][cnt] = max(f[l][r][cnt], f[l + 1][k - 1][0] + f[k][r][cnt - b[l]]);
f[l][r][0] = max(f[l][r][0], f[l][r][cnt] + cnt * cnt);
}
}
printf("Case %d: %d\n", C, f[1][m][0]);
}
}


#include<bits/stdc++.h>
using namespace std;
long long f[9][9][9][9][16]; // 均方差等式两边平方，然后同时乘n^3，避免分数
int n, a[9][9], sum[9][9];

inline long long sqr(long long x) {
return x * x;
}

inline int rect_sum(int u, int d, int l, int r) { // 二维子矩阵和
return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1];
}

int main() {
cin >> n;
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++) {
scanf("%d", &a[i][j]);
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
memset(f, 0x3f, sizeof(f));
for (int len_row = 1; len_row <= 8; len_row++)
for (int len_col = 1; len_col <= 8; len_col++)
for (int u = 1; u <= 8 - len_row + 1; u++) // up
for (int l = 1; l <= 8 - len_col + 1; l++) { // left
int d = u + len_row - 1; // down
int r = l + len_col - 1; // right
f[u][d][l][r][1] = sqr(n * rect_sum(u, d, l, r) - sum[8][8]);
for (int cnt = 2; cnt <= n; cnt++) { // 分成几块
for (int mid = u; mid < d; mid++) { // 横着切
f[u][d][l][r][cnt] = min(min(
f[u][mid][l][r][1] + f[mid + 1][d][l][r][cnt - 1], // 切掉上面一半
f[u][mid][l][r][cnt - 1] + f[mid + 1][d][l][r][1] // 切掉下面一半
), f[u][d][l][r][cnt]);
}
for (int mid = l; mid < r; mid++) { // 竖着切
f[u][d][l][r][cnt] = min(min(
f[u][d][l][mid][1] + f[u][d][mid + 1][r][cnt - 1], // 切掉左边一半
f[u][d][l][mid][cnt - 1] + f[u][d][mid + 1][r][1]
), f[u][d][l][r][cnt]);
}
}
}
cout << setprecision(3) << fixed << sqrt(f[1][8][1][8][n] * 1.0 / (n * n * n)) << endl;
}


#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 206;
ll a[N], f[N][N];

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);;
for (int i = n + 1; i <= n << 1; i++) a[i] = a[i-n];
for (int len = 3; len <= n + 1; len++)
for (int l = 1; l + len - 1 <= n << 1; l++) {
int r = l + len - 1;
for (int k = l + 1; k < r; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i][i+n]);
cout << ans << endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
int f[105][105], p[105][105], n;
char a[105];

bool equals(int r, int ed, int len) { // r,ed往前len个字符是否相同
for (int i = 0; i < len; i++)
if (a[r - i] != a[ed - i]) return false;
return true;
}

void print(int l, int r) {
if (!p[l][r]) {
for (int i = l; i <= r; i++) putchar(a[i]);
return;
}
if (p[l][r] > 0) {
print(l, p[l][r]);
print(p[l][r] + 1, r);
} else {
int len = -p[l][r];
printf("%d(", (r - l + 1) / len);
print(l, l + len - 1);
putchar(')');
}
}

int main() {
scanf("%s", a + 1);
n = strlen(a + 1);
memset(f, 0x3f, sizeof(f));
for (int len = 1; len <= n; len++)
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
// [l,r]拆分成两段
if (len == 1) f[l][r] = 1;
else for (int k = l; k < r; k++)
if (f[l][k] + f[k + 1][r] < f[l][r]) {
f[l][r] = f[l][k] + f[k + 1][r];
p[l][r] = k;
}
// [l,r]]重复cnt次生成更长的字符串[l,ed]
for (int ed = r + len, cnt = 2; ed <= n && equals(r, ed, len); ed += len, cnt++)
if (f[l][r] + 2 + std::to_string(cnt).length() < f[l][ed]) {
f[l][ed] = f[l][r] + 2 + std::to_string(cnt).length();
p[l][ed] = -len; // 负数表示由若干个长度为len的子串循环构成
}
}
print(1, n);
}


// Author: https://www.acwing.com/solution/content/12873/
#include <bits/stdc++.h>
using namespace std;

const int p = 10005;

int a[7], used[p << 1];
bool f[p];

int main()
{
while (true)
{
a[0] = 0;
for (int i = 1; i < 7; ++i)
cin >> a[i], a[0] += a[i] * i;

if (a[0] == 0) break;
if (a[0] & 1) { cout << "Can't\n"; continue; }
memset(f, 0, sizeof f);
a[0] >>= 1; f[0] = 1;

for (int i = 1; i < 7; ++i)
{
for (int j = 0; j <= a[0]; ++j) used[j] = 0;

for (int j = i; j <= a[0]; ++j)
if (!f[j] && f[j - i] && used[j - i] < a[i])
f[j] = 1, used[j] = used[j - i] + 1;
}

if (f[a[0]]) cout << "Can\n";
else cout << "Can't\n";
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int mod = 11380;
int f[31][11][11][11], L1, L2, L3, D;
int main() {
cin >> L1 >> L2 >> L3 >> D;
for (int i = 0; i <= D; i++) f[i][0][0][0] = 1;
for (int i = 1; i <= D; i++)
for (int j = 0; j <= L1; j++)
for (int k = 0; k <= L2; k++)
for (int l = 0; l <= L3; l++) {
if (j > 0) { // 第一段最外层是{}
for (int p = 1; p <= j; p++)
for (int q = 0; q <= k; q++)
for (int r = 0; r <= l; r++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][p - 1][q][r] * f[i][j - p][k - q][l - r]) % mod;
}
if (k > 0) { // 第一段最外层是[]
for (int q = 1; q <= k; q++)
for (int r = 0; r <= l; r++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][q - 1][r] * f[i][j][k - q][l - r]) % mod;
}
if (l > 0) { // 第一段最外层是()
for (int r = 1; r <= l; r++)
f[i][j][k][l] = (f[i][j][k][l] + f[i - 1][0][0][r - 1] * f[i][j][k][l - r]) % mod;
}
}
cout << (f[D][L1][L2][L3] - (D ? f[D - 1][L1][L2][L3] : 0) + mod) % mod << endl;
}


#include<bits/stdc++.h>
using namespace std;
const int T = 10000; // 平移避免负数
int a[105], n, t;
// f: 前i个数能否凑成j；g/s: true减号，false加号
bool f[105][20005], g[105][20005], s[105];

inline bool valid(int x) { return x >= -T && x <= T;}

void sign(int i, int j) {
if (i == 2) { s[1] = false, s[2] = true; return; }
s[i] = g[i][j + T];
if (s[i]) sign(i - 1, j + a[i]);
else sign(i - 1, j - a[i]);
}

int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
f[2][a[1] - a[2] + T] = true;
for (int i = 2; i < n; i++)
for (int j = -T; j <= T; j++)
if (f[i][j + T]) {
if (valid(j - a[i + 1])) { // i + 1前面是负号
f[i + 1][j - a[i + 1] + T] = true;
g[i + 1][j - a[i + 1] + T] = true;
}
if (valid(j + a[i + 1])) { // i + 1前面是正号
f[i + 1][j + a[i + 1] + T] = true;
g[i + 1][j + a[i + 1] + T] = false;
}
}
sign(n, t);
// for (int i = 1; i <= n; i++) printf("%c", s[i] ? '-' : '+');
// puts("");
int merged = 0;
// 先合并连续的加号
// 例如 1-2-3+4+5+6-7 变成 1-2-(3-4-5-6)-7，3456合并起来
for (int i = 2; i <= n; i++)
if (!s[i]) printf("%d\n", i - 1 - merged), merged++;
// 从左到右不断执行减号即可
for (int i = 2; i <= n; i++)
if (s[i]) puts("1");
}


#include<bits/stdc++.h>
using namespace std;
int f[82][82], n, m;
char a[82], b[82];
int preA[82][26], preB[82][26];
char ans[82];
vector<char> last[82][82];

void print(int i, int j, int len) {
if (f[i][j] == 1) {
ans[len] = 0;
puts(ans);
return;
}
for (int k = 0; k < last[i][j].size(); k++) {
char ch = last[i][j][k];
ans[len] = ch;
print(preA[i - 1][ch - 'a'], preB[j - 1][ch - 'a'], len + 1);
}
}

int main() {
scanf("%s%s", a + 1, b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
for (int i = 1; i <= n; i++) {
for (int ch = 0; ch < 26; ch++) preA[i][ch] = preA[i - 1][ch];
preA[i][a[i] - 'a'] = i;
}
for (int i = 1; i <= m; i++) {
for (int ch = 0; ch < 26; ch++) preB[i][ch] = preB[i - 1][ch];
preB[i][b[i] - 'a'] = i;
}
a[++n] = b[++m] = '\$';
memset(f, 0xcc, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) {
for (int ch = 'a'; ch <= 'z'; ch++) {
int pa = preA[i - 1][ch - 'a'];
int pb = preB[j - 1][ch - 'a'];
if (f[pa][pb] + 1 > f[i][j]) {
f[i][j] = f[pa][pb] + 1;
last[i][j].clear();
last[i][j].push_back(ch);
} else if (f[pa][pb] + 1 == f[i][j]) {
last[i][j].push_back(ch);
}
}
}
print(n, m, 0);
}


#include<bits/stdc++.h>
using namespace std;
int n, a[5005], f[5005], c[5005], ans, tot;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
a[0] = 1 << 30;
memset(f, 0xcc, sizeof(f));
f[0] = 0, c[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (a[j] > a[i]) {
// f[i] = max(f[i], f[j] + 1);
if (f[i] < f[j] + 1) f[i] = f[j] + 1, c[i] = c[j];
else if (f[i] == f[j] + 1) c[i] += c[j];
}
for (int i = 1; i <= n; i++)
if (f[i] > ans) ans = f[i], tot = c[i];
else if (f[i] == ans) tot += c[i];
cout << ans << ' ' << tot << endl;
}


#include <cstdio>
#include <iostream>
using namespace std;
const int N = 106, INF = 0x7fffffff;
int n, m, a[N][N], f[N][N], d[N][N], ans[N];

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= m - n + 1; i++) f[1][i] = a[1][i];
for (int i = 2; i <= n; i++) {
int k = -INF, t;
for (int j = i; j <= m - n + i; j++) {
if (k < f[i-1][j-1]) {
k = f[i-1][j-1];
t = j - 1;
}
f[i][j] = k + a[i][j];
d[i][j] = t;
}
}
int k = -INF, t;
for (int i = n; i <= m; i++)
if (k < f[n][i]) {
k = f[n][i];
t = i;
}
cout << k << endl;
int w = n;
while (t) {
ans[w] = t;
t = d[w--][t];
}
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
puts("");
return 0;
}