4_3

3985

anss

lty2019

runningboy001

DraymoNd_

nickelth
rushhhhh
usx123
carryking
JasonQ1an

Lucius7

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int w[N];
int f[N][N], g[N][N];

void dfs(int l, int r)
{
if (l > r) return;
int k = g[l][r];
cout << k << ' ';
dfs(l, k - 1);
dfs(k + 1, r);
}

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> w[i];

for (int len = 1; len <= n; len ++)
for (int l = 1; l + len - 1 <= n; l ++)
{
int r = l + len - 1;
if (len == 1) f[l][r] = w[l], g[l][r] = l;
else
{
for (int k = l; k <= r; k ++)
{
int left = k == l ? 1 : f[l][k - 1];
int right = k == r ? 1 : f[k + 1][r];
int score = left * right + w[k];
if (f[l][r] < score)
{
f[l][r] = score;
g[l][r] = k;
}
}
}
}

cout << f[1][n] << '\n';

dfs(1, n);

return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];

sort(a + 1, a + n + 1, greater<int>());

int res = 0;
for (int i = 1, j = n; i <= n; i ++)
{
while (j && a[j] < i) j --;
if (a[i] >= i - 1 && i <= m + j)
res = i;
}

cout << res << endl;
return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<string, int> id = {
{"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2},
{"Dragon", 3}, {"Snake", 4}, {"Horse", 5},
{"Goat", 6}, {"Monkey", 7}, {"Rooster", 8},
{"Dog", 9}, {"Pig", 10}, {"Rat", 11}
};

int main()
{
unordered_map<string, int> p;
p["Bessie"] = 0;

int n;
cin >> n;
while (n -- )
{
string s[8];
for (int i = 0; i < 8; i ++ ) cin >> s[i];

if (s[3] == "previous")
{
int x = p[s[7]], y = id[s[4]];
int r = ((x - y) % 12 + 12) % 12;
if (!r) r = 12;
p[s[0]] = x - r;
}
else
{
int x = p[s[7]], y = id[s[4]];
int r = ((y - x) % 12 + 12) % 12;
if (!r) r = 12;
p[s[0]] = x + r;
}
}

cout << abs(p["Elsie"]) << endl;
return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

int n;
int f[N][N];
int w[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> w[i];
w[i + n] = w[i];
}

for (int len = 2; len <= n; len ++)
for (int l = 1; l + len <= n << 1; l ++)
{
int r = l + len;
for (int k = l + 1; k < r; k ++)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}

int res = 0;
for (int i = 1; i <= n << 1; i ++)
res = max(res, f[i][i + n]);

cout << res << endl;
return 0;
}



4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int f[N][N], g[N][N];
int w[N], s[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> w[i];
w[i + n] = w[i];
}

for (int i = 1; i <= n << 1; i ++)
s[i] = s[i - 1] + w[i];

memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);

for (int len = 1; len <= n; len ++)
for (int l = 1; l + len - 1 < n << 1; l ++)
{
int r = l + len - 1;
if (l == r) f[l][r] = g[l][r] = 0;
else
{
for (int k = l; k < r; k ++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}

int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i ++)
{
maxv = max(maxv, g[i][i + n - 1]);
minv = min(minv, f[i][i + n - 1]);
}

cout << minv << '\n' << maxv << '\n';
return 0;
}


4_3
1个月前

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110, M = 65;

int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;

bool check(int state)
{
return !(state & state >> 1 || state & state >> 2);
}
int count(int state)
{
int res = 0;
while (state) res += state & 1, state >>= 1;
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < m; j ++)
{
char c;
cin >> c;
if (c == 'H') g[i] += 1 << j;
}

for (int i = 0, j = 0; i < 1 << m; i ++)
if (check(i))
{
state.push_back(i);
cnt[j ++] = count(i);
}

for (int i = 0; i < state.size(); i ++)
for (int j = 0; j < state.size(); j ++)
if (!(state[i] & state[j]))

for (int i = 1; i <= n + 2; i ++)
for (int a = 0; a < state.size(); a ++)
if (!(state[a] & g[i]))
for (int b: head[a])
for (int c: head[b])
if (!(state[a] & state[c]))
f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]);

cout << f[n + 2 & 1][0][0] << '\n';
return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int g[N];
int f[2][M];
vector<int> state;

bool check(int state)
{
return !(state & state >> 1);
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < m; j ++)
{
int x;
cin >> x;
if (!x) g[i] |= 1 << j;
}

for (int i = 0; i < 1 << m; i ++)
if (check(i))
state.push_back(i);

for (int a: state)
for (int b: state)
if (!(a & b))

f[0][0] = 1;
for (int i = 1; i <= n + 1; i ++)
for (int a: state)
{
f[i & 1][a] = 0;
if (!(a & g[i]))
for (int b: head[a])
f[i & 1][a] = (f[i & 1][a] + f[i - 1 & 1][b]) % mod;
}

cout << f[n + 1 & 1][0] << '\n';
return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, k;
LL f[N][K][M];
int cnt[M];
vector<int> state;

bool check(int state)
{
return !(state & state >> 1);
}

int count(int state)
{
int res = 0;
for (int i = 0; i < n; i ++)
res += state >> i & 1;
return res;
}

int main()
{
cin >> n >> k;

for (int i = 0; i < 1 << n; i ++)
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}

for (int i = 0; i < state.size(); i ++)
for (int j = 0; j < state.size(); j ++)
{
int a = state[i], b = state[j];
if ((a & b) == 0 && check(a | b))
}

f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i ++)
for (int j = 0; j <= k; j ++)
for (int a = 0; a < state.size(); a ++)
{
f[i & 1][j][a] = 0;
for (int b: head[a])
{
int c = cnt[state[a]];
if (j >= c)
f[i & 1][j][a] += f[i - 1 & 1][j - c][b];
}
}

cout << f[n + 1 & 1][k][0] << '\n';
return 0;
}


4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1e9 + 7;

int n;
char s[N];
int ne[N], f[N][N];

int main()
{
cin >> n >> s + 1;
int m = strlen(s + 1);

for (int i = 2, j = 0; i <= m; i ++)
{
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j ++;
ne[i] = j;
}

f[0][0] = 1;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
for (int k = 'a'; k <= 'z'; k ++)
{
int u = j;
while (u && s[u + 1] != k) u = ne[u];
if (s[u + 1] == k) u ++;
f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
}

int res = 0;
for (int i = 0; i < m; i ++) res = (res + f[n][i]) % MOD;

cout << res << '\n';
return 0;
}


4_3
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int w[N], f[N][3];

int main()
{
cin >> n;
for  (int i = 1; i <= n; i ++)
cin >> w[i];

f[0][2] = f[0][1] = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++)
{
f[i][0] = max(f[i - 1][0], f[i - 1][2]);
f[i][1] = max(f[i - 1][0] - w[i], f[i - 1][1]);
f[i][2] = f[i - 1][1] + w[i];
}

cout << max(f[n][0], f[n][2]) << endl;
return 0;
}