状态机

f[i][j][1] : 只考虑前i天， 已经完成 j - 1次交易， 正在进行第j次交易且手中有货（正在买第j次交易的股票，交易才开始）
f[i][j][0] : 只考虑前i天，已经完成j-1次交易，正在进行第j次交易且手中无货（把第j次交易的股票卖掉了，第j次交易完成）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010, M = 110;

int f[N][M][2];
int n, m;
int w[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[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][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
        }
    }

    int res = 0;
    for(int i = 1; i <= m; i ++) res = max(res, f[n][i][0]);
    printf("%d\n", res);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;

int w[N];
int f[N][2];
int t, n;

void solve()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    f[0][0] = 0, f[0][1] = -1;
    for(int i = 1; i <= n; i ++)
    {
        f[i][1] = f[i - 1][0] + w[i];
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
    }
    printf("%d\n", max(f[n][0], f[n][1]));
}

int main()
{
    scanf("%d", &t);
    while(t --)
        solve();
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;

struct Node
{
    int l, r;
    ll sum; // 区间和 考虑当前节点及子节点上的所有标记，当前区间和是多少
    ll add; // 懒标记 给当前区间的所有儿子加上add
} tr[N << 2];
ll a[N];
int n, m;

void pushup(Node &fa, Node &l, Node &r)
{
    fa.sum = l.sum + r.sum;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u)
{
    Node &fa = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.add += fa.add, l.sum += (ll)(l.r - l.l + 1) * fa.add;
    r.add += fa.add, r.sum += (ll)(r.r - r.l + 1) * fa.add;
    fa.add = 0;
}

void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[r], 0};
    }
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, ll v)
{
    if(l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].sum += v * (tr[u].r - tr[u].l + 1);
        tr[u].add += v;
    }
    else // 一定要分裂
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, v);
        if(r > mid) modify(u << 1 | 1, l, r, v);
        pushup(u);
    }
}

ll query(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        ll sum = 0;
        if(l <= mid) sum += query(u << 1, l, r);
        if(r > mid) sum += query(u << 1 | 1, l ,r);
        return sum;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    build(1, 1, n);

    char op[2];
    int l, r;
    while(m --)
    {
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q')
        {
            printf("%lld\n", query(1, l, r));
        }
        else
        {
            ll d;
            scanf("%lld", &d);
            modify(1, l, r, d);
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;

int n;
int a[N];
int cnt[N];
int ans[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

    for(int i = 0; i < n; i ++)
    {
        memset(cnt, 0, sizeof cnt);
        int t = 0;
        for(int j = i; j < n; j ++)
        {
            int x = a[j];
            cnt[x] ++;
            if((cnt[x] == cnt[t] && x < t) || cnt[x] > cnt[t])
                t = x;
            ans[t] ++;
        }
    }
    for(int i = 1; i <= n; i ++)
        printf("%d ", ans[i]);
    return 0;
}

bfs

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
typedef pair<string, string> PII;
int res = 100;
string res_op;

string A(string s)
{
    string t = s;
    reverse(t.begin(), t.end());
    return t;
}

string B(string s)
{
    string t = s.substr(0, 3) + s.substr(5);
    t = s[3] + t + s[4];
    return t;
}

string C(string s)
{
    string t = s;
    char tt = t[1];
    t[1] = t[6];
    t[6] = t[5];
    t[5] = t[2];
    t[2] = tt;
    return t;
}

void bfs(string start, string aim)
{
    queue<PII> q;
    unordered_map<string, int> mp;
    mp[start] ++;
    q.push({start, ""});
    while(q.size())
    {
        auto t = q.front(); q.pop();
        string ts = t.first, tp = t.second;
        if(ts == aim)
        {
            res = tp.size();
            res_op = tp;
            return;
        }
        string tmp = A(ts);
        if(!mp[tmp])
        {
            q.push({tmp, tp + 'A'});
            mp[tmp] ++;
        }
        tmp = B(ts);
        if(!mp[tmp])
        {
            q.push({tmp, tp + 'B'});
            mp[tmp] ++;
        }
        tmp = C(ts);
        if(!mp[tmp])
        {
            q.push({tmp, tp + 'C'});
            mp[tmp] ++;
        }
    }
}

int main()
{
    string start = "12345678";
    string aim = "00000000";
    for(int i = 0; i < 8; i ++)
    {
        int x;
        cin >> x;
        aim[i] = (aim[i] + x);
    }
    bfs(start, aim);
    cout << res << endl;
    if(res)
        cout << res_op << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 22;

string word[N];
int g[N][N]; // g[i][j] 第j个单词接到第i个单词后面最小公共部是多长
int used[N]; // used[i] 第i个单词被使用了几次
int n;
char start;
int res = 1;
// 当前龙  龙的最后用的哪个单词
void dfs(string dragon, int u)
{
    res = max((int)dragon.size(), res);
    for(int i = 1; i <= n; i ++)
    {
        if(g[u][i] && used[i] < 2)
        {
            used[i] ++;
            dfs(dragon + word[i].substr(g[u][i]), i);
            used[i] --;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> word[i];
    cin >> start;

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            for(int k = 1; k < min((int)word[i].size(), (int)word[j].size()); k ++)
            {
                if(word[i].substr(word[i].size() - k) == word[j].substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }

    // 枚举以哪个单词开始
    for(int i = 1; i <= n; i ++)
        if(word[i][0] == start)
        {
            used[i] ++;
            dfs(word[i], i);
            used[i] --;
        }

    cout << res << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 22;

string word[N];
int g[N][N]; // g[i][j] 第j个单词接到第i个单词后面最小公共部是多长
int used[N]; // used[i] 第i个单词被使用了几次
int n;
char start;
int res = 1;
// 当前龙  龙的最后用的哪个单词
void dfs(string dragon, int u)
{
    used[u] ++;
    res = max((int)dragon.size(), res);
    for(int i = 1; i <= n; i ++)
    {
        if(g[u][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[u][i]), i);
    }
    used[u] --;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> word[i];
    cin >> start;

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            for(int k = 1; k < min((int)word[i].size(), (int)word[j].size()); k ++)
            {
                if(word[i].substr(word[i].size() - k) == word[j].substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }

    // 枚举以哪个单词开始
    for(int i = 1; i <= n; i ++)
        if(word[i][0] == start)
            dfs(word[i], i);

    cout << res << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 28;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
bool g[N][N];
int n, m;
int res;

void dfs(int x, int y, int cnt)
{
    if(cnt == n * m) res ++;
    for(int i = 0; i < 8; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || b < 0 || a >= n || b >= m) continue;
        if(!g[a][b])
        {
            g[a][b] = true;
            dfs(a, b, cnt + 1);
            g[a][b] = false;
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int x, y;
        cin >> n >> m >> x >> y;
        memset(g, 0, sizeof g);
        g[x][y] = true;
        res = 0;
        dfs(x, y, 1);
        cout << res << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 28;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
bool g[N][N];
int n, m;
int res;

bool check()
{
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(!g[i][j]) return false;
    return true;
}

void dfs(int x, int y)
{
    if(check()) res ++;
    for(int i = 0; i < 8; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || b < 0 || a >= n || b >= m) continue;
        if(!g[a][b])
        {
            g[a][b] = true;
            dfs(a, b);
            g[a][b] = false;
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int x, y;
        cin >> n >> m >> x >> y;
        memset(g, 0, sizeof g);
        g[x][y] = true;
        res = 0;
        dfs(x, y);
        cout << res << endl;
    }
    return 0;
}

dfs

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char g[N][N];
bool st[N][N];
int n, m;

int dfs(int x, int y)
{
    st[x][y] = true;
    int cnt = 1;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || b < 0 || a >= n || b >= m) continue;
        if(st[a][b] || g[a][b] == '#') continue;
        cnt += dfs(a, b);
    }
    return cnt;
}

int main()
{
    while(cin >> m >> n, n)
    {
        int x, y;
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < m; j ++)
            {
                cin >> g[i][j];
                if(g[i][j] == '@') x = i, y = j;
            }
        }
        memset(st, false, sizeof st);
        cout << dfs(x, y) << endl;
    }
    return 0;
}

bfs

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 22;
typedef pair<int, int> PII;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char g[N][N];
bool st[N][N];
int n, m;

int bfs(PII start)
{
    memset(st, false, sizeof st);
    int res = 1;
    queue<PII> q;
    q.push({start.x, start.y});
    st[start.x][start.y] = true;
    while(q.size())
    {
        auto t = q.front(); q.pop();
        for(int i = 0; i < 4; i ++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a <= 0 || b <= 0 || a > n || b > m) continue;
            if(g[a][b] == '#' || st[a][b]) continue;
            q.push({a, b});
            st[a][b] = true;
            res ++;
        }
    }
    return res;
}

int main()
{
    while(cin >> m >> n, n && m)
    {
        PII start;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= m; j ++)
            {
                cin >> g[i][j];
                if(g[i][j] == '@') start = {i, j};
            }
        }
        int res = bfs(start);
        cout << res << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char g[N][N];
bool st[N][N];
int t, n;
int x1, y1, x2, y2;

bool dfs(int x, int y)
{
    st[x][y] = true;
    if(g[x][y] == '#') return false; // 特判起点或则终点就是#
    if(x == x2 && y == y2) return true;
    bool flag = false;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i];
        int b = y + dy[i];
        if(a < 0 || b < 0 || a >= n || b >= n) continue;
        if(st[a][b] || g[a][b] == '#') continue;
        flag |= dfs(a, b);
    }
    return flag;
}

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> g[i];
        cin >> x1 >> y1 >> x2 >> y2;
        memset(st, false, sizeof st);
        if(dfs(x1, y1))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;
string s;
char c1, c2;
int f[N]; // f[i] :位置i及前面c1出现的次数
int k;

int main()
{
    cin >> k;
    cin >> s;
    cin >> c1;
    cin >> c2;
    s = '@' + s;
    f[0] = 0;
    int len = s.size();
    for(int i = 1; i <= len; i ++)
        if(s[i] == c1) f[i] = f[i - 1] + 1;
        else f[i] = f[i - 1];
    ll res = 0;
    for(int i = k; i <= len; i ++)
        if(s[i] == c2) res += f[i - k + 1];
    cout << res << endl;
    return 0;
}