limcc

2100

limcc
13天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int w[N][N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= i; j ++)
cin >> w[i][j];
}
for (int i = 1; i <= n; i ++)
f[n][i] = w[n][i];
for (int i = n - 1; i; i --)
{
for (int j = 1; j <= i; j ++)
{
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
}
}
cout << f[1][1];
return 0;
}


limcc
17天前
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
sort(a, a + n);
long long res = 0;
for (int i = 0; i < n; i ++)
res += abs(a[n / 2] - a[i]);
cout << res << endl;
return 0;
}


limcc
2个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;
int f[N][N], w[N][N];
int n, m;
int main()
{
int T;
scanf("%d", &T);
while (T --)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
{
f[i][j] = 0;
scanf("%d", &w[i][j]);
}
int sum = 0;
for (int i = 0; i < n; i ++) sum += w[i][0], f[i][0] = sum;
sum = 0;
for (int j = 0; j < m; j ++) sum += w[0][j], f[0][j] = sum;
for (int i = 1; i < n; i ++)
for (int j = 1; j < m; j ++)
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
printf("%d\n", f[n - 1][m - 1]);
}
return 0;
}


limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, k;
int quicksort(int a[], int l, int r, int k)
{
if (l >= r) return a[l];
int i = l - 1, j = r + 1;
int x = a[l + r >> 1];
while (i < j)
{
do i ++; while (a[i] < x);
do j --; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
int sl = j - l + 1;
if (k <= sl) return quicksort(a, l, j, k);
return quicksort(a, j + 1, r, k - sl);  // 注意这里
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
printf("%d\n", quicksort(a, 0, n - 1, k));
return 0;
}


limcc
5个月前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int r, c;
int f[N][N], a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int dp(int x, int y)
{
if (f[x][y] != -1) return f[x][y];
f[x][y] = 1;  // 务必注意初始化，只走当前这格
for (int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] < a[x][y])
{
f[x][y] = max(f[x][y], dp(nx, ny) + 1);
}
}
return f[x][y];
}
int main()
{
scanf("%d%d", &r, &c);
int res = 0;
for (int i = 1; i <= r; i ++)
{
for (int j = 1; j <= c; j ++)
scanf("%d", &a[i][j]);
}
memset(f, -1, sizeof f);
for (int i = 1; i <= r; i ++)
{
for (int j = 1; j <= c; j ++)
res = max(res, dp(i, j));
}
printf("%d\n", res);
return 0;
}


limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6010;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx ++;
}
void dfs(int u)
{
f[u][1] = happy[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
dfs(j);

f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
int main()
{
memset(h, -1, sizeof h);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%d", &happy[i]);
for (int i = 0; i < n - 1; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
has_fa[a] = true;
}
int root = 1;
while (has_fa[root]) root ++;
dfs(root);
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}码要放在两组三个点之间，才可以正确显示代码高亮哦~


limcc
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1010, mod = 1e9 + 7;
ll f[N][N];
int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; ++ i) f[i][0] = 1;  // 从1-i中选，和为0，只能全部都不选这一种选法
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= n; ++ j)
{
f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
if (j >= i) f[i][j] = (f[i][j] + f[i][j - i]) % mod;
}
}
printf("%d\n", f[n][n]);
return 0;
}


limcc
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
typedef pair<int, int> PII;
typedef long long ll;
PII cow[N];  // 存储s+w, w
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
{
int w, s;
scanf("%d%d", &w, &s);
cow[i] = {w + s, s};  // 存储w+s和s
}
sort(cow, cow + n);
int res = -2e9, sum = 0;
for (int i = 0; i < n; ++ i)
{
int s = cow[i].second, w = cow[i].first - s;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}


limcc
5个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
struct Range
{
int l, r;
bool operator < (const Range &w)const
{
return l < w.l;
}
}range[N];
int main()
{
int st, ed;
scanf("%d%d", &st, &ed);
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
{
int l, r;
scanf("%d%d", &l, &r);
range[i] = {l, r};
}
sort(range, range + n);
bool success = false;  // 标记是否成功
int res = 0;
for (int i = 0; i < n; ++ i)
{
int j = i, max_r = -2e9;  //记录能覆盖左端点的区间的最大右端点
while (j < n && range[j].l <= st)
{
max_r = max(range[j].r, max_r);  // 找到区间的最大右端点
j ++;
}
if (max_r < st)  // 最大右端点都比木棒的左端点小，说明没有区间能覆盖
{
res = -1;
break;
}
res ++;  // 可以覆盖
if (max_r >= ed)  // 最大右端点已经可以覆盖木棒右端点，结束
{
success = true;
break;
}
st = max_r;  // 木棒左端点更新成最大右端点
i = j - 1;  // 注意这里，后面++i的时候才会变成j
}
if (!success) printf("%d\n", -1);
else printf("%d\n", res);
return 0;
}


limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
sort(a, a + n);
ll res = 0;
for (int i = 0; i < n; ++ i)
{
res += abs(a[i] - a[n / 2]);
}
cout << res << endl;
return 0;
}