TYNFMS https://tynfms.github.io/

1.8万

1..
tingze
Jixer

high-DIO
rizon
mmkl

Lts

b11

fly_fish
decoder
20090331

2个月前
// Problem: 传纸条
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/277/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 60;
int g[N][N], f[N << 1][N][N];
int n, m;

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

for (int k = 2; k <= n + m; k++)
for (int x1 = max(1, k - m); x1 <= n && x1 < k; x1++) // 1 <= y1 = k - x1 <= m, 1 <= x1 <= n => 1 1
for (int x2 = max(1, k - m); x2 <= n && x2 < k; x2++)
for (int a = 0; a <= 1; a++)
for (int b = 0; b <= 1; b++) {
int y1 = k - x1, y2 = k - x2;
int tmp = g[x1][y1];
if (x1 != x2 || k == 2 || k == n + m) {
tmp += g[x2][y2];
f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + tmp);
}
}
// {
// if (x1 == x2) continue;
// int y1 = k - x1, y2 = k - x2;
// // (x1 - 1, y1), (x2 - 1, y2)
// // (x1, y1 - 1), (x2 - 1, y2)
// // (x1 - 1, y1), (x2, y2 - 1)
// // (x1, y1 - 1), (x2, y2 - 1)
// f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - 1][x2 - 1]);
// f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1][x2 - 1]);
// f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - 1][x2]);
// f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1][x2]);
// f[k][x1][x2] += g[x1][y1] + g[x2][y2];
// }

cout << f[n + m][n][n] << endl;

return 0;
}



2个月前
// Problem: 移动服务
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/276/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 210, M = 1010;
const int INF = 0x3f3f3f3f;
int g[N][N], n, m;
int request[M];
int f[M][N][N];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &g[i][j]);
for (int i = 1; i <= m; i++)
scanf("%d", request + i);

request[0] = 3;
memset(f, 0x3f, sizeof(f));
f[0][1][2] = 0;
for (int i = 0; i < m; i++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++) {
int z = request[i], v = f[i][x][y];
if (x == y || y == z || z == x) continue;
int u = request[i + 1];
f[i + 1][y][z] = min(f[i + 1][y][z], v + g[x][u]);
f[i + 1][x][z] = min(f[i + 1][x][z], v + g[y][u]);
f[i + 1][x][y] = min(f[i + 1][x][y], v + g[z][u]);
}

int res = INF;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++) {
int z = request[m];
if (x == y || y == z || z == x) continue;
res = min(res, f[m][x][y]);
}
printf("%d\n", res);

return 0;
}



2个月前
// Problem: 分级
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/275/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010;
const int INF = 0x3f3f3f3f;
int a[N], n, b[N];
int f[N][N];

int solve() {
for (int i = 1; i <= n; i++) {
int minv = INF;
for (int j = 1; j <= n; j++) {
minv = min(minv, f[i - 1][j]);
f[i][j] = minv + abs(a[i] - b[j]);
}
}

int res = INF;
for (int i = 1; i <= n; i++)
res = min(res, f[n][i]);
return res;
}

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

sort(b + 1, b + n + 1);
int res = solve();
reverse(a + 1, a + n + 1);
res = min(res, solve());

cout << res << endl;

return 0;
}



2个月前
// Problem: 最长公共上升子序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/274/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 3010;
int f[N][N], n, a[N], b[N];

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

for (int i = 1; i <= n; i++) {
int maxv = 1;
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}

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

return 0;
}


2个月前
// Problem: 杨老师的照相排列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/273/
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 31;
int n, a[N];
ll f[N][N][N][N][N];

int main() {
while (cin >> n && n) {
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(f, 0, sizeof(f));
f[0][0][0][0][0] = 1;

for (int a1 = 0; a1 <= a[1]; a1++)
for (int a2 = 0; a2 <= min(a1, a[2]); a2++)
for (int a3 = 0; a3 <= min(a2, a[3]); a3++)
for (int a4 = 0; a4 <= min(a3, a[4]); a4++)
for (int a5 = 0; a5 <= min(a4, a[5]); a5++) {
ll &x = f[a1][a2][a3][a4][a5];
if (a1 && a1 - 1 >= a2) x += f[a1 - 1][a2][a3][a4][a5];
if (a2 && a2 - 1 >= a3) x += f[a1][a2 - 1][a3][a4][a5];
if (a3 && a3 - 1 >= a4) x += f[a1][a2][a3 - 1][a4][a5];
if (a4 && a4 - 1 >= a5) x += f[a1][a2][a3][a4 - 1][a5];
if (a5)                 x += f[a1][a2][a3][a4][a5 - 1];
}

cout << f[a[1]][a[2]][a[3]][a[4]][a[5]] << endl;
}

return 0;
}


3个月前
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 12, M = 1 << N;
const int INF = 0x3f3f3f3f;
int n, m;
int d[N][N];
int f[M][N], g[M];

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

memset(d, 0x3f, sizeof(d));
for (int i = 0; i < n; i++)
d[i][i] = 0;

while (m--) {
int x, y, z;
cin >> x >> y >> z;
x--, y--;
d[x][y] = d[y][x] = min(d[x][y], z);
}

for (int i = 1; i < 1 << n; i++)
for (int j = 0; j < n; j++)
if (i >> j & 1) {
for (int k = 0; k < n; k++)
if (d[j][k] != INF)
g[i] |= 1 << k;
}

memset(f, 0x3f, sizeof(f));
for (int i = 0; i < n; i++)
f[1 << i][0] = 0;

for (int i = 1; i < 1 << n; i++)
for (int j = i - 1 & i; j; j = (j - 1) & i)
if ((g[j] & i) == i) {
int rest = i ^ j;
int cost = 0;
for (int k = 0; k < n; k++)
if (rest >> k & 1) {
int t = INF;
for (int x = 0; x < n; x++)
if (j >> x & 1)
t = min(t, d[k][x]);
cost += t;
}

for (int k = 1; k < n; k++)
f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
}

int res = INF;
for (int i = 0; i < n; i++)
res = min(res, f[(1 << n) - 1][i]);
cout << res << endl;

return 0;
}


3个月前
#include <iostream>
using namespace std;

const int N = 1010;
int n;
int a[N];
int l[N][N], r[N][N];

int main() {
int tt;
cin >> tt;
while (tt--) {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int len = 1; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (len == 1) l[i][j] = r[i][j] = a[i];
else {
int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
if (R == X) l[i][j] = 0;
else if (X < L && X < R || X > L && X > R) l[i][j] = X;
else if (L > R) l[i][j] = X - 1;
else l[i][j] = X + 1;

L = l[i + 1][j], R = r[i + 1][j], X = a[i];
if (L == X) r[i][j] = 0;
else if (X < L && X < R || X > L && X > R) r[i][j] = X;
else if (R > L) r[i][j] = X - 1;
else r[i][j] = X + 1;
}
}

if (n == 1) puts("1");
else cout << (l[2][n] != a[1]) << endl;
}

return 0;
}


3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 14;
const double INF = 1e20;
int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y) {
if (a > 13 || b > 13 || c > 13 || d > 13)
return INF;
double &v = f[a][b][c][d][x][y];
if (v >= 0) return v;
int as = a + (x == 0) + (y == 0);
int bs = b + (x == 1) + (y == 1);
int cs = c + (x == 2) + (y == 2);
int ds = d + (x == 3) + (y == 3);
if (as >= A && bs >= B && cs >= C && ds >= D)
return v = 0;

int sum = a + b + c + d + (x != 4) + (y != 4);
sum = 54 - sum;
if (sum <= 0) return v = INF;

v = 1;
if (a < 13) v += (13. - a) / sum * dp(a + 1, b, c, d, x, y);
if (b < 13) v += (13. - b) / sum * dp(a, b + 1, c, d, x, y);
if (c < 13) v += (13. - c) / sum * dp(a, b, c + 1, d, x, y);
if (d < 13) v += (13. - d) / sum * dp(a, b, c, d + 1, x, y);
if (x == 4) {
double t = INF;
for (int i = 0; i < 4; i++)
t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
v += t;
}
if (y == 4) {
double t = INF;
for (int i = 0; i < 4; i++)
t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
v += t;
}

return v;
}

int main() {
cin >> A >> B >> C >> D;
memset(f, -1, sizeof(f));

double t = dp(0, 0, 0, 0, 4, 4);
if (t > INF / 2.) t = -1;
printf("%.3lf\n", t);

return 0;
}


3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dout[N];
double f[N];

inline void add(int x, int y, int z) {
e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}

double dp(int x) {
if (f[x] >= 0.) return f[x];
f[x] = 0.;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i], z = w[i];
f[x] += (z + dp(y)) / dout[x];
}
return f[x];
}

int main() {
scanf("%d%d", &n, &m);

for (int i = 0, x, y, z; i < m; i++) {
scanf("%d%d%d", &x, &y, &z);
dout[x]++;
}

memset(f, -1, sizeof(f));

printf("%.2lf\n", dp(1));

return 0;
}


3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 50010;
int primes[N], cnt;
bool vis[N];
int mobius[N], sum[N];

void init(int n) {
mobius[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
primes[cnt++] = i;
mobius[i] = -1;
}
for (int j = 0; primes[j] * i <= n; j++) {
int tmp = primes[j] * i;
vis[tmp] = 1;
if (!(i % primes[j])) {
mobius[tmp] = 0;
break;
}
mobius[tmp] = -mobius[i];
}
}

for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + mobius[i];
}

int main() {
init(N - 1);

int tt;
scanf("%d", &tt);
while (tt--) {
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
a /= d, b /= d;
int n = min(a, b);
ll res = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n, min(a / (a / l), b / (b / l)));
res += 1ll * (sum[r] - sum[l - 1]) * (a / l) * (b / l);
}

cout << res << endl;
}

return 0;
}