8878

### 二分

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
pair<int, int> a[N];
int maxnum = -1;
int main()
{

cin >> n >> k;

for (int i = 0; i < n; i++) {
int c, b;
cin >> c >> b;
maxnum = max(maxnum, c);
maxnum = max(maxnum, b);
a[i] = make_pair(c, b);
}
int l = 0, r = maxnum;
while (l < r) {
//本题求最大值 属于红色部分
//采用第一二分法
int mid = l + r + 1 >> 1;
int sum = 0;
for (int i = 0; i < n; i++) {
int n1, n2;
n1 = a[i].first / mid;
n2 = a[i].second / mid;
sum += n1 * n2;
}
//符合条件时
if (sum >=k) {
l= mid;
}
//不符合条件时
else r = mid -1;
}
cout << l << endl;
system("PAUSE");
return 0;

}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int h[N];
int f[N];
int main() {

int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <=n; i++) {
cin >> h[i];
}
int res = 0;
for (int i = 1; i <=n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (h[i] < h[j])
f[i] = max(f[i], f[j] + 1);

}
res = max(res, f[i]);
}
memset(f, 0, sizeof(f));
for (int i = n; i > 0; i--) {
f[i] = 1;
for (int j = n; j > i; j--) {
if (h[i] < h[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << res << endl;
}
return 0;
}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int h[N];
int f[N];
int main() {

int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <=n; i++) {
cin >> h[i];
}
int res = 0;
for (int i = 1; i <=n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (h[i] < h[j])
f[i] = max(f[i], f[j] + 1);

}
res = max(res, f[i]);
}
memset(f, 0, sizeof(f));
for (int i = n; i > 0; i--) {
f[i] = 1;
for (int j = n; j > i; j--) {
if (h[i] < h[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
cout << res << endl;
}
return 0;
}


1个月前

### 第四题 传纸条

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int g[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}

for (int k = 2; k <= n + m; k++) {
for (int i = max(1, k - m); i <= n && i < k; i++) {
for (int j = max(1, k - m); j <= n && j < k; j++) {
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
int t = g[i][k - i];
if (i != j || k == 2 || k == n + m) {
t += g[j][k - j];
f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
}
}
}
}
}
}
cout << f[n + m][n][n] << endl;

return 0;
}


1个月前

### 第四题 传纸条

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int g[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}

for (int k = 2; k <= n + m; k++) {
for (int i = max(1, k - m); i <= n && i < k; i++) {
for (int j = max(1, k - m); j <= n && j < k; j++) {
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
int t = g[i][k - i];
if (i != j || k == 2 || k == n + m) {
t += g[j][k - j];
f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
}
}
}
}
}
}
cout << f[n + m][n][n] << endl;

return 0;
}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n;
int a, b, c;
while (cin >> a >> b >> c)w[a][b] = c;

//因为从(1,1)开始 k=1+1=2
for (int k = 2; k <= n + n; k++) {
for (int i1 = 1; i1 <= n; i1++) {
for (int i2 = 1; i2 <= n; i2++) {
int j1 = k - i1;
int j2 = k - i2;
if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int t = w[i1][j1];
if (i1 != i2)t += w[i2][j2];
int& x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
cout << f[n + n][n][n] << endl;
return 0;
}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main()
{
cin >> n;
int a, b, c;
while (cin >> a >> b >> c)w[a][b] = c;

//因为从(1,1)开始 k=1+1=2
for (int k = 2; k <= n + n; k++) {
for (int i1 = 1; i1 <= n; i1++) {
for (int i2 = 1; i2 <= n; i2++) {
int j1 = k - i1;
int j2 = k - i2;
if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int t = w[i1][j1];
if (i1 != i2)t += w[i2][j2];
int& x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
cout << f[n + n][n][n] << endl;
return 0;
}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int f[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof(f));

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1) {
f[i][j] = w[i][j];
}
else {
f[i][j] = min(f[i][j], f[i - 1][j]+w[i][j]);
f[i][j] = min(f[i][j], f[i][j - 1]+w[i][j]);
}
}
}
cout << f[n][n] << endl;

return 0;
}


1个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int f[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof(f));

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1) {
f[i][j] = w[i][j];
}
else {
f[i][j] = min(f[i][j], f[i - 1][j]+w[i][j]);
f[i][j] = min(f[i][j], f[i][j - 1]+w[i][j]);
}
}
}
cout << f[n][n] << endl;

return 0;
}