二分

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

}

正反做两遍LIS
当固定方向后 最长距离是以a[i]为结尾的最长上升子序列

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

正反做两遍LIS
当固定方向后 最长距离是以a[i]为结尾的最长上升子序列

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

第四题 传纸条

去一趟 回来一趟 可以看成是从起点走到终点两趟
两次不能走相同的格子

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

第四题 传纸条

去一趟 回来一趟 可以看成是从起点走到终点两趟
两次不能走相同的格子

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

一个地图走两次，求两次路径的取物品价值最大问题

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

一个地图走两次，求两次路径的取物品价值最大问题

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

根据题目分析 必须是2N-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;
}

根据题目分析 必须是2N-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;
}