#include<bits/stdc++.h> usingnamespacestd; #define N 100001 int h[N], f[N], n, k; intmain(){ scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &h[i]); for (int i = 2; i <= n; i++) { int minn = 2147483647; for (int j = max(1, i - k); j < i; j++) minn = min(minn, abs(h[i] - h[j]) + f[j]); f[i] = minn; } printf("%d\n", f[n]); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define N 100001 int s[N][3], f[N][3], n; intmain(){ scanf("%d", &n); for (int k = 1; k <= n; k++) for (int i = 0; i < 3; i++) scanf("%d", &s[k][i]); for (int k = 1; k <= n; k++) for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) f[k][i] = max(f[k][i], f[k - 1][j] + s[k][i]); printf("%d\n", max(max(f[n][0], f[n][1]), f[n][2])); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define N 100001 ll f[N]; int n, m; intmain(){ scanf("%d%d", &n, &m); for (int i = 1, w, v; i <= n; i++) { scanf("%d%d", &w, &v); for (int j = m; j >= w; j--) f[j] = max(f[j], f[j - w] + v); } printf("%lld\n", f[m]); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define N 100001 ll f[N]; int n, m; intmain(){ memset(f, 0x3f, sizeof(f)); f[0] = 0; scanf("%d%d", &n, &m); for (int i = 1, w, v; i <= n; i++) { scanf("%d%d", &w, &v); for (int j = N - 1; j >= v; j--) f[j] = min(f[j], f[j - v] + w); } int add = N - 1; while (f[add] > m) add--; printf("%d\n", add); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define N 100001 #define M 100001 int hd[N], nx[M], e[M]; int f[N], v[N], n, m; intdfs(int x){ if (f[x]) return f[x]; for (int i = hd[x]; i; i = nx[i]) f[x] = max(f[x], dfs(e[i])); return ++f[x]; } intmain(){ scanf("%d%d", &n, &m); for (int i = 1, Num = 0, x, y; i <= m; i++) { scanf("%d%d", &x, &y); nx[++Num] = hd[x], hd[x] = Num, e[Num] = y; } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dfs(i)); printf("%d\n", ans - 1); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define N 301 int num[4], n; double p[N][N][N]; doubleP(int x, int y, int z){ if (p[x][y][z] >= 0) return p[x][y][z]; double sum = (double)n / (x + y + z); if (x) sum += P(x - 1, y, z) * x / (x + y + z); if (y) sum += P(x + 1, y - 1, z) * y / (x + y + z); if (z) sum += P(x, y + 1, z - 1) * z / (x + y + z); return p[x][y][z] = sum; } intmain(){ scanf("%d", &n); for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) p[i][j][k] = -1; p[0][0][0] = 0; for (int i = 1, x; i <= n; i++) { scanf("%d", &x); num[x]++; } printf("%.10lf\n", P(num[1], num[2], num[3])); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define N 101 #define M 100001 int a[N], f[M] = {-1}, n, m; intsearch(int num){ if (f[num]) return f[num]; bool flag = false; for (int i = 1; i <= n; i++) if (a[i] <= num && search(num - a[i]) == -1) flag = true; return f[num] = (flag ? 1 : -1); } intmain(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); puts(search(m) == 1 ? "First" : "Second"); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define N 401 ll f[N][N], s[N][N]; int a[N], n; intmain(){ memset(f, 0x3f, sizeof(f)); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); f[i][i] = 0, s[i][i] = a[i]; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) s[i][j] = s[i][j - 1] + a[j]; for (int len = 1; len < n; len++) { for (int i = 1; i + len <= n; i++) { int j = i + len; for (int k = i; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[i][j]); } } printf("%lld\n", f[1][n]); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define mod 1000000007 #define N 10001 int a[N], d; ll f[N][101]; ll dfs(int len, int pre, int top){ if (!len) return pre == 0; if (!top && f[len][pre] != -1) return f[len][pre]; int up = top ? a[len] : 9; ll num = 0; for (int i = 0; i <= up; i++) num = (num + dfs(len - 1, (pre + i) % d, top && (i == up))) % mod; if (!top) f[len][pre] = num; return num; } char c[N]; intmain(){ memset(f, -1, sizeof(f)); scanf("%s%d", c + 1, &d); int n = strlen(c + 1); for (int i = n, j = 1; i; i--, j++) a[j] = c[i] - '0'; cout << (dfs(n, 0, 1) - 1 + mod) % mod << endl; return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define M 65536 #define N 16 int a[N][N], v[N], n; ll sum[M], f[M]; intmain(){ scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]); for (int t = 0; t < (1 << n); t++) { int num = 0; for (int i = 0; i < n; i++) if (t >> i & 1ll) v[num++] = i; ll s = 0; for (int i = 0; i < num; i++) for (int j = i + 1; j < num; j++) s += a[v[i]][v[j]]; f[t] = sum[t] = s; } for (int i = 0; i < (1 << n); i++) for (int j = i; j; j = (j - 1) & i) f[i] = max(f[i], f[i ^ j] + sum[j]); printf("%lld\n", f[(1 << n) - 1]); return0; }
#include<bits/stdc++.h> usingnamespacestd; #define ll long long #define M 20001 #define N 1001 structfaner { int w, s, v; } a[N]; ll f[M], ans; boolcmp(faner a, faner b){ return a.s + a.w < b.s + b.w; } int n; intmain(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].w, &a[i].s, &a[i].v); sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++) for (int j = M - 1; j >= a[i].w; j--) if (a[i].s + a[i].w >= j) f[j] = max(f[j], f[j - a[i].w] + a[i].v); for (int i = 1; i < M; i++) ans = max(ans, f[i]); printf("%lld\n", ans); return0; }