#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

struct Node
{
    int x;
    string s;
}node[N];

bool cmp(Node &a, Node &b)
{
    return a.x > b.x;
}

int main()
{
    int n; cin >> n;
    for(int j = 0; j < n; j ++)
    {
        int x; cin >> x;
        string op; cin >> op;
        node[j] = {x, op};
    }

    sort(node, node + n, cmp);

    for(int i = 0; i < n; i ++)
        cout << node[i].s << endl;

    return 0;
}

#include<iostream>

using namespace std;

const int N = 15;
int f[N];

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

    int tmax = 0;
    for(int i = 0; i < n; i ++)
    {
        string s; cin >> s;
        int a = s[0] - '0', b = s.back() - '0';
        f[b] = max(f[b], f[a] + 1);
        tmax = max(tmax, f[b]);
    }

    cout << n - tmax;

    return 0;
}

状态表示 f[i] 前i个餐馆中满足条件的最大值

状态转移先二分出距离第i个餐馆大于k距离的餐馆j 存在的话f[i] = max(f[i - 1], f[j] + w[i]);

不存在的话f[i] = max(f[i - 1], w[i]);

时间复杂度 $O(nlogn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

int f[N];
int a[N], w[N];

int main()
{
    int T; cin >> T;
    while(T --)
    {
        int n, k;
        cin >> n >> k;
        memset(a, 0, sizeof a);
        memset(w, 0, sizeof w);
        for(int j = 1; j <= n; j ++)cin >> a[j];
        for(int j = 1; j <= n; j ++)cin >> w[j];

        f[1] = w[1];
        for(int j = 2; j <= n; j ++)
        {
            f[j] = 0;
            int l = 1, r = n;
            while(l < r)
            {
                int mid = (l + r + 1) >> 1;
                if(a[j] - a[mid] > k)l = mid;
                else r = mid - 1;
            }
            if(a[j] - a[l] > k)
                f[j] = max(f[l] + w[j], f[j - 1]);
            else f[j] = max(f[j - 1], w[j]);
        }
        cout << f[n] << endl;
    }
    return 0;
}

主要是为了练习最简单的线段树（hh）

C++1 代码 部分超时

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 1000010;

struct date
{
    int l, r;
    int tmax;
}dates[N * 4];
int n, k;

void build(int u, int l, int r)
{
    dates[u].l = l, dates[u].r = r;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void updatemax(int u)
{
    dates[u].tmax = min(dates[u << 1].tmax, dates[u << 1 | 1].tmax);
}

void add(int u, int x, int y)
{
    if(dates[u].l == dates[u].r && dates[u].l == x)
        dates[u].tmax = y;
    else {
        int mid = (dates[u].l + dates[u].r) >> 1;
        if(mid >= x)add(u << 1, x, y);
        else add(u << 1 | 1, x, y);
        updatemax(u);
    }
}

int quire(int u, int l, int r)
{
    int dl = dates[u].l, dr = dates[u].r;
    if(l <= dl && r >= dr)return dates[u].tmax;

    int tmax = 0x3f3f3f3f;
    int mid = (dl + dr) >> 1;
    if(l <= mid)tmax = quire(u << 1, l, r);
    if(r > mid)tmax = min(tmax, quire(u << 1 | 1, l, r));
    return tmax;
}

int main()
{
    cin >> n;
    build(1, 1, n);

    for(int j = 1; j <= n; j ++)
    {
        int x; cin >> x;
        add(1, j, x);
    }

    cin >> k;

    for(int j = 1; j <= n; j ++)
    {
        int l = max(j - k, 1);
        int r = min(j + k, n);
        cout << quire(1, l, r) << ' ';
    }

    return 0;
}

c++代码2 数据输入的优化处理（没有add函数直接在update中实现）

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 1000010;

struct date
{
    int l, r;
    int tmax;
}dates[N * 4];
int n, k;
int w[N];

void updatemax(int u)
{
    dates[u].tmax = min(dates[u << 1].tmax, dates[u << 1 | 1].tmax);
}

void build(int u, int l, int r)
{
    if(l == r)
  {
    dates[u] = {l, r, w[l]};
    return;
  }
  else {
    dates[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    updatemax(u);
  }
}

int quire(int u, int l, int r)
{
    int dl = dates[u].l, dr = dates[u].r;
    if(l <= dl && r >= dr)return dates[u].tmax;

    int tmax = 0x3f3f3f3f;
    int mid = (dl + dr) >> 1;
    if(l <= mid)tmax = quire(u << 1, l, r);
    if(r > mid)tmax = min(tmax, quire(u << 1 | 1, l, r));
    return tmax;
}

int main()
{
    cin >> n;

    for(int j = 1; j <= n; j ++)
    cin >> w[j];

  build(1, 1, n);

    cin >> k;

    for(int j = 1; j <= n; j ++)
    {
        int l = max(j - k, 1);
        int r = min(j + k, n);
        cout << quire(1, l, r) << ' ';
    }

    return 0;
}

对于第一个物品用完全背包问题来装 对于后m个物品使用多重背包问题来装即可 （背包板子题）

C++ 代码如下

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int f[N];
int n, m, v, w;
vector<PII>ve;

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

    for(int j = 1; j <= m; j ++)
    {
        int v0, w0;
        int x, y; cin >> x >> y >> v0 >> w0;
        int cnt = x / y;
        int k = 1;
        while(k <= cnt)
        {
            ve.push_back({k * v0, k * w0});
            cnt -= k;
            k *= 2;
        }
        if(cnt > 0)ve.push_back({cnt * v0, w0 * cnt});
    }

    for(auto x : ve)
    {
        for(int j = n; j >= x.first; j --)
        {
            f[j] = max(f[j], f[j - x.first] + x.second);

        }
    }

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

    cout << f[n];

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int f[N];
int n, m, v, w;
vector<PII>ve;

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

    for(int j = 1; j <= m; j ++)
    {
        int v0, w0;
        int x, y; cin >> x >> y >> v0 >> w0;
        int cnt = x / y;
        int k = 1;
        while(k <= cnt)
        {
            ve.push_back({k * v0, k * w0});
            cnt -= k;
            k *= 2;
        }
        if(cnt > 0)ve.push_back({cnt * v0, w0 * cnt});
    }

    for(auto x : ve)
    {
        for(int j = n; j >= x.first; j --)
        {
            f[j] = max(f[j], f[j - x.first] + x.second);

        }
    }

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

    cout << f[n];

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5010;

int a[N], idx;
int f[N][N];

int main()
{
    int n; cin >> n;
    while (n -- )
    {
        int x; cin >> x;
        if(x == a[idx])continue;
        a[++idx] = x;
    }

    // cout << idx << endl;
    // for(int j = 1; j <= idx; j ++)cout << a[j] << ' ';
    // puts("");

    for(int len = 2; len <= idx; len ++)
    {
        for(int l = 1, r = l + len - 1; r <= idx; l ++, r ++)
        {
            if(a[l] == a[r])f[l][r] = f[l + 1][r - 1] + 1;
            else f[l][r] = min(f[l + 1][r], f[l][r - 1]) + 1;
        }
    }

    cout << f[1][idx];
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 50010;

int f[N], g[N];
int a[N];

int main()
{
    int T; cin >> T;
    while(T --) 
    {
        int n; cin >> n;

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

        memset(f, -0x3f, sizeof f);
        memset(g, -0x3f, sizeof g);

        int s = 0;
        for(int j = 1; j <= n; j ++)
        {
            s = max(s, 0) + a[j];
            f[j] = max(s, f[j - 1]);
        }


        s = 0;
        for(int j = n; j > 0; j --)
        {
            s = max(s, 0) + a[j];
            g[j] = max(s, g[j + 1]);
        }

        int res = -0x3f3f3f3f;
        for(int j = 1; j < n; j ++)
        {
            res = max(res, f[j] + g[j + 1]);
        }

        cout << res << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    cout << max(abs(a - c), abs(b - d));

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100, M = 1000010, mod = 1e9;
typedef long long LL;

int a[N], idx;
LL f[M];

void init()
{
    for(int j = 1; j <= 1e6; j <<= 1)
    {
        a[++ idx] = j;
    }
}

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

    f[0] = 1;
    for(int j = 1; j <= idx; j ++)
    {
        for(int i = a[j]; i <= n; i ++ )
        {
            f[i] = (f[i] + f[i - a[j]]) % mod;
        }
    }

    cout << f[n];

    return 0;
}