StarLi9ht

1316

Sherlock_0
arch_hui

Eaf_quakee
Shmilysw

yxc

XX31MRK

Atopos_

GeekAlice

StarLi9ht
12小时前

1.完全背包写法

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main()
{
cin >> n;

f[0] = 1;

for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
f[j] = (f[j] + f[j - i]) % mod;

cout << f[n] << endl;

return 0;
}


2.另一种算法

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

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

int main()
{
cin >> n;

f[1][1] = 1;

for (int i = 2; i <= n; i ++)
for (int j = 1; j <= i; j ++)
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

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

cout << res << endl;

return 0;
}


StarLi9ht
17小时前

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


memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= m; i ++) f[0][i] = i;
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 ++) f[i][0] = i;


StarLi9ht
18小时前
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20;

int n, m;
char a[N][M], b[M];
int f[M][M];

int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", a[i] + 1);

while (m --) {
int t;
scanf("%s%d", b + 1, &t);
int m1 = strlen(b + 1);

int res = 0;
for (int k = 0; k < n; k ++)
{
int n1 = strlen(a[k] + 1);

for (int i = 1; i <= m1; i ++) f[0][i] = i;
for (int i = 1; i <= n1; i ++) f[i][0] = i;

for (int i = 1; i <= n1; i ++)
for (int j = 1; j <= m1; j ++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[k][i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}

if (f[n1][m1] <= t) res ++;
}

printf("%d\n", res);
}

return 0;
}


StarLi9ht
18小时前

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);

for (int i = 1; i <= m; i ++) f[0][i] = i;
for (int i = 1; i <= n; i ++) f[i][0] = i;

for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}

printf("%d\n", f[n][m]);

return 0;
}


StarLi9ht
20小时前

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int a[N];
int q[N];  // q[i] 表示 长度为i的最长上升子序列 的末尾最小值

int main() {
scanf("%d", &n);xiaozhi
for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);

int len = 0;
for (int i = 0; i < n; i ++)
{
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}

printf("%d\n", len);

return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

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

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

for (int len = 2; len <= n; len ++)
for (int i = 1; i + len - 1 <= n; i ++)
{
int l = i, r = i + len - 1;
f[l][r] = 1e9;
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]);
}

printf("%d\n", f[1][n]);

return 0;
}


注意！！！

1. f[i-1][j] 不等价于 01 这种情况，但 f[i-1][j]是包含 01 这种情况的，由于本题是求最大值，所以集合划分可以重复

2. 由于 f[i-1][j-1] 既包含于 f[i-1][j] ，又包含于 f[i][j-1]，所以f[i-1][j-1]可以省略

3. 只有当a[i] == b[j]时，才可以考虑 11这种情况

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);

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]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}

printf("%d\n", f[n][m]);

return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

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

for (int i = 1; i <= n; i ++)
{
f[i] = 1; //只有a[i]一个数
for (int j = 1; j < i; j ++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}

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

cout << res << endl;

return 0;
}


可以通过记录状态转移 来记录最佳方案

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

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

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

for (int i = 1; i <= n; i ++)
{
f[i] = 1; //只有a[i]一个数
for (int j = 1; j < i; j ++)
if (a[j] < a[i])
if (f[i] < f[j] + 1)
{
f[i] = f[j] + 1;
g[i] = j;
}

}

int k = 0;
for (int i = 1; i <= n; i ++)
if (f[k] < f[i])
k = i;

cout << f[k] << endl;

for (int i = 0, len = f[k]; i < len; i ++)
{
cout << a[k] << ' ';
k = g[k];
}

return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

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

for (int i = 1; i <= n; i ++)
for (int j = 0; j <= i + 1; j ++)
f[i][j] = -INF;

f[1][1] = a[1][1];
for (int i = 2; i <= n; i ++)
for (int j = 1; j <= i; j ++)
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

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

printf("%d\n", res);

return 0;
}