718

wmh123
acwing9876

ACALL139

acwing_1914
ForwardForever
CVer
Catw1thu
acgangster
dp_5

tonpirdrea

#include <iostream>

using namespace std;

const int N = 1010;
int n, m, f[N][N];
string a, b;

int main() {
cin >> n >> a >> m >> b;
a = " " + a;
b = " " + b;

for (int i = 1; i <= n; i++) f[i][0] = i;
for (int i = 1; i <= m; i++) f[0][i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
// f[i][j] a的1~i子串变成b的1~j子串，至少需要进行的次数
// 最后一步是增加最后一个字母 | 最后一步是删除最后一个字母 | 最后一步是修改最后一个字母
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
}
cout << f[n][m];
}



#include <iostream>

using namespace std;

const int N = 1010, M = 1e9 + 7;
int n, f[N][N] ;

int main() {
cin >> n;

f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (j - i >= 0)
f[i][j] = (f[i][j] + f[i][j - i]) % M;
}
cout << f[n][n];
}



#include <iostream>
#include <cstring>

using namespace std;

const int N = 310;
int n, a[N], f[N][N];

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

memset(f, 0x3f, sizeof f);
for (int l = 0; l < n; l++)
for (int i = 1; i + l <= n; i++) {
if (l == 0) {
f[i][i] = 0;
continue;
}
int j = i + l;
for (int k = i; k < j; k++)
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
}
cout << f[1][n];
}



#include<iostream>

using namespace std;

const int N = 12010, M = 2010;

int n, m, v[N], w[N], f[M];

int main() {
cin >> n >> m;
int cnt = 0;  // 将n种物品打包成cnt个组，每组是一个选择方案
for (int i = 1; i <= n; i++) {
int a, b, s;
cin >> a >> b >> s;
for (int k = 1; k <= s; k *= 2) {  // 分别打包成1、2、4……个位一组
cnt++;  // 组别先增加
v[cnt] = a * k;  // 该打包组的体积
w[cnt] = b * k;  // 该打包组的价值
s -= k;  // s要减小
}
if (s > 0) {  // 剩余的一组
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

// 枚举次数n由个数变成组数。多重背包转为01背包
for (int i = 1; i <= cnt; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;
int n, sum, ans = -0x3f3f3f3f;
pair<int, int> a[N];

int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int w, s;
cin >> w >> s;
a[i] = {w + s, w};
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
int w = a[i].second, s = a[i].first - a[i].second;
ans = max(ans, sum - s);
sum += w;
}
cout << ans;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N];
long long ans;

int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);

for (int i = 0; i < n; i++) ans += abs(a[i] - a[n / 2]);
cout << ans;
}



#include <iostream>
#include <queue>

using namespace std;

const int N = 100010;
int n;
long long ans;
priority_queue<int, vector<int>, greater<>> heap;

int main() {
cin >> n;
for (int i = 0, t; i < n; i++) {
cin >> t;
heap.push(t);
}

while (!heap.empty()) {
ans += heap.top() * (heap.size() - 1);
heap.pop();
}
cout << ans;
}



#include <iostream>
#include <queue>

using namespace std;

const int N = 10010;
int n, res;
priority_queue<int, vector<int>, greater<>> heap;

int main() {
cin >> n;
for (int i = 0, t; i < n; i++) {
cin >> t;
heap.push(t);
}

while (!heap.empty()) {
int c = heap.top();
heap.pop();
if (heap.empty()) break;
c += heap.top();
heap.pop();
heap.push(c);
res += c;
}

cout << res;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, st, ed, res;
pair<int, int> a[N];
bool succ;

int main() {
cin >> st >> ed >> n;
for (int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;

sort(a, a + n);
for (int i = 0; i < n;) {
int j = i, r = -2e9;  // j为候选区间，r是最右边界
while (j < n && a[j].first <= st) {  // 还有区间并且能覆盖目标左边界
r = max(r, a[j].second);  // 找最右边界
j++;
}
if (r < st) break;
res++;
if (r >= ed) {
succ = true;
break;
}
i = j;
st = r;
}
if (!succ) res = -1;
cout << res;
}



#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int n;
PII a[N];
priority_queue<int, vector<int>, greater<>> heap;  // !注意堆的语法

int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

sort(a, a + n);

for (int i = 0; i < n; i++) {
int l = a[i].first, r = a[i].second;
if (heap.empty() || l <= heap.top())
;
else
heap.pop();
heap.push(r);
}
cout << heap.size();
}