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

const int N = 1e5+10,M = 110;
int a[N];
int f[N][M][2];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> a[i];
    memset(f,-0x3f,sizeof f);
    for(int i = 0; i <= n; i ++ ) f[i][0][0] = 0;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - a[i]);
        }
    }
    int res = 0;
    for(int i = 0; i <= m; i ++ )
        res = max(res,f[n][i][0]);
    cout << res << "\n";
    return 0;

}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 40;

int n;
int w[N];
vector<int> level[N];

int getmin(int l, int r)
{
    int res = l;
    for (int i = l; i <= r; i ++ )
        if (w[res] > w[i])
            res = i;
    return res;
}

void dfs(int l, int r, int d)
{
    if (l > r) return;
    int root = getmin(l, r);
    level[d].push_back(w[root]);
    dfs(l, root - 1, d + 1);
    dfs(root + 1, r, d + 1);
}

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

    dfs(0, n - 1, 0);
    for (int i = 0; level[i].size(); i ++ )
        for (auto x: level[i])
            cout << x << ' ';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1010;
int f[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    while(cin >> m >> n)
    {
        for(int i = 0; i <= n; i ++ ) f[i][0] = 1;
        for(int i = 0; i <= m; i ++ ) f[1][i] = 1;
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= m; j ++ )
            {
                if(j < i) f[i][j] = f[j][j];
                else 
                {
                    f[i][j] = f[i-1][j] + f[i][j - i];
                }
            }
        } 
        cout << f[n][m] << "\n";
    }

    return 0;

}

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

const int N = 1010;
int f[N][N],g[N][N];

int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int n;
int dfs(int x,int y)
{
    if(f[x][y] != -1) return f[x][y];
    f[x][y] = 1;
    for(int i = 0; i < 4; i ++ )
    {
       int a = x + dx[i],b = y + dy[i];
       if(a >= 1 and a <= n and b >= 1 and b <= n and g[x][y] + 1 == g[a][b])
       {
            f[x][y] = max(f[x][y], dfs(a,b) + 1);
       }
    }
    return f[x][y];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        cin >> n;
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                cin >> g[i][j];
        memset(f,-1,sizeof f);
        int res = 0,cnt = 0;
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= n; j ++ )
            {
                int t = dfs(i,j);
                if(t > cnt or g[i][j] < res and t == cnt)
                {
                    res = g[i][j];//当前几号点
                    cnt = t;//走了几步
                }
            }
        }
        cout << "Case #" << i << ": " << res << " " << cnt << "\n";

    }
    return 0;

}

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

const int N = 200100;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++ )
            cin >> a[i];
        int res = 0;
        for(int i = 0; i < n; i ++ )
        {
            int j = i + 2;
            while(j < n and a[j] - a[j - 1] == a[j - 1] - a[j - 2]) j ++;
            res = max(res,j - i);
            i = j - 2;
        }
        cout << "Case #" << i << ": ";
        cout << res << "\n";

    }
    return 0;

}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        int n;
        cin >> n;
        unordered_map<string,int> m1;
        unordered_map<string,string> m2;
        while(n -- )
        {
            string a,b;
            cin >> a >> b;
            m1[a] ++,m1[b] ++,m2[a] = b;
        }
        string r;
        for(auto t : m1)
        {
            if(t.second == 1 and m2.count(t.first))
                r = t.first;
        }
         cout << "Case #" << i << ": ";
        for(string i = r; m2.count(i); i = m2[i]) 
            cout << i << "-" << m2[i] << " ";
        cout << "\n";
    }
    return 0;

}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int a = 0,b = 0;
    for(int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        a += x;
    }
    for(int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        b += x;
    }
    if(a >= b) cout << "Yes\n";
    else cout << "No\n";
    return 0;

}

y总

#include <cstring>
#include <iostream>

using namespace std;

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

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

int main()
{
    cin >> n >> m;

    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1;

    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- )
        {
            int maxv = max(f[j], f[j - v] + w);
            int s = 0;
            if (f[j] == maxv) s = g[j];
            if (f[j - v] + w == maxv) s = (s + g[j - v]) % mod;
            f[j] = maxv, g[j] = s;
        }
    }

    int res = 0;
    for (int i = 1; i <= m; i ++ )
        if (f[i] > f[res])
            res = i;

    int sum = 0;
    for (int i = 0; i <= m; i ++ )
        if (f[i] == f[res])
            sum = (sum + g[i]) % mod;

    cout << sum << endl;

    return 0;
}

稽宝

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

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

int f[N],cnt[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    for(int i = 0; i <= m; i ++ )
        cnt[i] = 1;
    for(int i = 0; i < n; i ++ )
    {
        int v,w;
        cin >> v >> w;
        for(int j = m; j >= v; j -- )
        {
            int maxx = f[j - v] + w;
            if(maxx > f[j]) //价值最大,选其求方案数
            {
                f[j] = maxx;
                cnt[j] = cnt[j - v] % mod;
            } 
            else if (maxx == f[j]) //相等, 更新两个的总和为方案数
            {
                cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            }
        }
    }
    cout << cnt[m] << "\n";
    return 0;

}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, s1, s2;

    char c;
    while (cin >> c, c != ',') s += c;
    while (cin >> c, c != ',') s1 += c;
    while (cin >> c) s2 += c;

    if (s.size() < s1.size() or s.size() < s2.size()) puts("-1");
    else
    {
        int l = 0;
        while (l + s1.size() <= s.size())
        {
            int k = 0;
            while (k < s1.size())
            {
                if (s[l + k] != s1[k]) break;
                k ++ ;
            }
            if (k == s1.size()) break;
            l ++ ;
        }
        int r = s.size() - s2.size();
        while (r >= 0)
        {
            int k = 0;
            while (k < s2.size())
            {
                if (s[r + k] != s2[k]) break;
                k ++ ;
            }
            if (k == s2.size()) break;
            r -- ;
        }

        l += s1.size() - 1;

        if (l >= r) puts("-1");
        else printf("%d\n", r - l - 1);
    }
    return 0;

}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string str;
    while (cin >> str, str != ".")
    {
        int len = str.size();

        for (int n = len; n; n -- )
            if (len % n == 0)
            {
                int m = len / n;
                string s = str.substr(0, m);
                string r;
                for (int i = 0; i < n; i ++ ) r += s;

                if (r == str)
                {
                    cout << n << endl;
                    break;
                }
            }
    }
    return 0;

}