1. Xiao mingai attends class [dynamic planning]

Xiao Ming likes classes very much. Now Xiao Ming has some classes in his schedule. He can choose which classes to take through the schedule.

There will be rewards for classes. The rewards will vary with the length of each class. There will be longer classes and fewer rewards. The total duration of each course is an integer. Rewards with different length will be given in the title data.

For each course, Xiao Ming can only take it once. Now Xiao Ming has a total of m minutes to arrange the class. But Xiao Ming wants to get the biggest reward. Can you help Xiao Ming solve this problem?

input

First line, enter two numbers n and m，Indicates the number of courses and the time Xiao Ming needs to attend. The following includes n Rows, per row m Number, No i Number indicates that for each class i Minutes bonus (i Starting from 1, each course can only be taken once)
For 10%Data for, 1<= n<= 4，1<=m<=4
 For 50%Data for, 1<= n<= 100，1<=m<=100
 For 100%Data for, 1<= n<=100，1<=m<=100
1<=Reward value<=1000

output

Output a number that represents the maximum reward value.

sample input

2 3
3 2 1
3 2 1

sample output

6

code

#include<bits/stdc++.h>
using namespace std;

int n, m, dp[105][105], credit[105][105];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> credit[i][j];
    for (int i = 1; i <= n; ++i) {  // Course i
        for (int s = 1; s <= m; ++s) {
            dp[i][s] = dp[i - 1][s];  // No course i
            for (int j = 1; j <= s; ++j) {
                dp[i][s] = max(dp[i][s], credit[i][j] + dp[i - 1][s - j]);
            }
        }
    }
    cout << dp[n][m];
    
    return 0;
}

2. Cut wood [two points]

There are n wooden sticks of different lengths. Now they should be cut into m wooden sticks of the same length, and the length of each section is an integer. How long can this m stick be?

If it cannot be separated, 0 is output.

input

Number of 2 in the first line: n, m Space between(1 <= n <= 100000, 1 <= m <= 10^9)
behind n Row: 1 number per row, corresponding to the length of the stick(1 <= Li <= 10^9). 

output

Output an integer corresponding to the length of the stick.

sample input

3 10
15
25
12

sample output

5

code

#include<bits/stdc++.h>
using namespace std;

int n, m, nums[100005];

bool check(int x) {
    int ans = 0;
    for (int i = 0; i < n; ++i) ans += (nums[i] / x);
    return ans >= m;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> nums[i];
    int lo = 1, hi = 1000000005;
    while (lo < hi) {
        int mi = lo + ((hi - lo) >> 1);
        check(mi) ? lo = mi + 1 : hi = mi;
    }
    cout << --lo;
    return 0;
}

3. How many blocks are there at most [greedy]

Little b has an array a of length n, which she wants to sort.

However, little b is very lazy. She thinks it is too tired to sort the whole array, so she asks you to divide a into some blocks so that she can sort the whole array only by sorting each block separately.

How many pieces of a can you divide at most.

An arrangement in which a is guaranteed to be 0... n-1.

Example explanation:

If a is divided into two or more blocks, the desired results cannot be obtained.
For example, it is divided into [4, 3], [2, 1, 0], and the result of sorting is [3, 4, 0, 1, 2], which is not an ordered array.

input

One number in the first line n；
Second line n Number representation a[i]，Separated by spaces.
n<=10

output

Output a number to indicate the number of partitions

sample input

5
4 3 2 1 0

sample output

5

code

#include<bits/stdc++.h>

using namespace std;

int n, nums[100005];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> nums[i];
    int ans = 0;
    for (int i = 0, maxNumber = -1; i < n; ++i) {
        maxNumber = max(maxNumber, nums[i]);
        if (maxNumber == i) ans++;
    }
    cout << ans;
    return 0;
}

4. Hide and seek [DFS]

In an 8*8 two-dimensional plane, you are at the M point at the initial time. For each mobile round, you can walk 1 grid in the direction of 8 Unicom, or you can stay where you are. You need to move to escape point A and stay safe until your next move round.

There are many cats in the box, which is indicated by S. You move first in each move round. After you move, all cats will move down one grid at the same time (in the bottom row of the two-dimensional plane, if the cat moves down, it will be regarded as moving out of the plane and will no longer appear). After all cat movements are completed, this movement round is deemed to have ended.

Ask if you can finally move from point M to point A to escape. If possible, output Win; otherwise, output Lost.

input

Input a total of 8 lines, and the characters in each line include'A' 'M' 'S' '.'，among M Indicates the starting position, A Indicates the end position, S Means cat,.It means open space. You can go anywhere.

output

Output a total of 1 line, if you can M Point move to A Point. output Win，Otherwise output Lost. 

sample input

.......A
........
........
........
........
........
SS......
M.......

sample output

Lost

code

#include<bits/stdc++.h>

using namespace std;

const vector<pair<int, int>> DIR{{0,  0}, {0,  1}, {0,  -1}, {1,  0}, {-1, 0},
                                 {1,  1}, {1,  -1}, {-1, 1}, {-1, -1}};
int xt, yt;
bool isCat[8][8];

bool dfs(int xi, int yi, int time) {
    if (xi < 0 || yi < 0 || xi == 8 || yi == 8) return false; // Boundary judgment
    if (time > 0 && xi - time + 1 > 0 && isCat[xi - time + 1][yi]) return false; // Captured by a cat (previous status)
    if (xi - time > 0 && isCat[xi - time][yi]) return false; // Captured by cat (current status)
    if ((xi == xt && yi == yt) || time == 8) return true;  // All cats remove the boundary, and there is always a path to the end
    return any_of(DIR.begin(), DIR.end(), [&](const pair<int, int> dir) {
        return dfs(xi + dir.first, yi + dir.second, time + 1);
    });
}

int main() {
    int xi, yi;
    string s;
    for (int i = 0; i < 8; ++i) {
        cin >> s;
        for (int j = 0; j < 8; ++j) {
            switch (s[j]) { // I haven't used the switch for a long time. I use it on a whim
                case 'S': isCat[i][j] = true; break;
                case 'M': xi = i, yi = j; break;
                case 'A': xt = i, yt = j; break;
            }
        }
    }
    cout << (dfs(xi, yi, 0) ? "Win" : "Lost");

    return 0;
}

5. Struggle for passage [dynamic planning]

Life is like a boat sailing against the current. In your life n n n stages, each stage has a lower limit of status L i L_i Li, there is also a status upper limit R i R_i Ri, you want to plan the status values of each stage of your life so that your status can be n n It is always getting better in n stages (strictly increasing). Please calculate how many different life plans there are. Because the answer is large, only the result of 998244353998244353 is output

Data range: 1 ≤ n ≤ 200 , 1 ≤ L i ≤ R i ≤ 104 1≤n≤200,1≤L_i≤R_i≤104 1≤n≤200,1≤Li​≤Ri​≤104

input

One integer in the first line n，Indicates the number of stages in life.
next n Rows, two integers per row Li, Ri，Indicates the lower and upper limits of the status values for this phase.

output

Output only one line, indicating the number of schemes mod 998244353 Results of.

sample input

4
1 6
3 5
1 4
4 6

sample output

4

code

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;

ull dp[205][10005];
int lim[205][2];

int main() {
    auto &lim_ = lim;
    auto &dp_ = dp;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> lim[i][0] >> lim[i][1];
    dp[0][0] = 1ll; // boundary condition 
    for (int i = 1, L, R; i <= n; ++i) {
        L = lim[i][0], R = lim[i][1];
        ull sum = 0;
        for (int j = 0; j < L; ++j) sum += dp[i - 1][j] % 998244353;
        for (int j = L; j <= R; ++j) {
            dp[i][j] = sum;
            sum += dp[i - 1][j] % 998244353;
        }
    }
    ull ans = 0;
    for (int j = lim[n][0]; j <= lim[n][1]; ++j) {
        ans += dp[n][j] % 998244353;
    }
    cout << ans % 998244353;

    return 0;
}