goontry

dongporen.github.io

goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 1; j <= s[i]; j++)
cin >> v[i][j] >> w[i][j];
}

for (int i = 1; i <= n; i++)
for (int j = m; j >= 0; j--)
for (int k = 1; k <= s[i]; k++)
{
if (v[i][k] <= j) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}

cout << f[m] << endl;

return 0;
}


goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000;

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

int main()
{
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int a, b, s;
cin >> a >> b >> s;

int k = 1;
while(k <= s)
{
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)
{
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

n = cnt;
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;
}


goontry
10个月前

### 暴力法 O(nmk)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
for (int k = 1; k <= s[i]; k++)
{
if (v[i] * k <= j)  f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
}

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

return 0;
}


goontry
10个月前

### 暴力法 o(nmk)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

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

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
for (int k = 1; j >= v[i] * k; k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
}

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

return 0;
}


### 等式变化 O(nm)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

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

for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if (v[i] <= j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}

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

return 0;
}


### 降维优化 O(nm)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

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

for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}

cout << f[m] << endl;

return 0;
}


goontry
10个月前

### 暴力法 O(nm)

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N][N];

int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i], cin >> w[i];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= V; j ++)
{
f[i][j] = f[i - 1][j];
if (v[i] <= j)
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}

cout << f[n][V] << endl;

return 0;
}


### 优化版本

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N];

int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i], cin >> w[i];

for (int i = 1; i <= n; i++)
for (int j = V; j >= v[i]; j--)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}

cout << f[V] << endl;

return 0;
}


goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

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


goontry
10个月前
#include <iostream>
#include <algorithm>

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;
}


goontry
10个月前
#include <iostream>
#include <algorithm>

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

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

return 0;
}


goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];

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

for (int i = 0; i <= n + 1; 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], f[i-1][j]) + a[i][j];

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

return 0;
}


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

const int N = 1e5 + 10;
int n;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int main()
{
scanf("%d", &n);
while (n--)
{
int a, b;
scanf("%d%d", &a, &b);
int res = gcd(a, b);
printf("%d\n", res);
}
return 0;
}