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

using namespace std;

const int N = 4010, M = 6010;

int n, m, cnt, f[M], v[N], w[N];

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

    cnt = 0;
    for (int i=1; i<=n; i++)
    {
        register int vv, ww, s;
        cin >> vv >> ww >> s;

        int p = 1;
        while (p <= s) {
            v[++cnt] = vv * p, w[cnt] = ww * p;
            s -= p;
            p <<= 1;
        }
        if ( s > 0 ) v[++cnt] = s*vv, w[cnt] = s*ww;
    }
    for (int i=1; i<=cnt; i++) 
        for (int j=m; j>=v[i]; j--) 
            f[j] = max(f[j], f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

不太懂，需要反复看

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

using namespace std;

const int N = 20010;

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

int main()
{
    cin >> n >> m;
    for (int i=0; i<n; i++) 
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);

        for (int j=0; j<v; j++) 
        {
            int hh = 0, tt = -1; 
            for (int k=j; k<=m; k+=v)
            {
                // 队首在滑动窗口外面
                if (hh <= tt && q[hh] < k - s*v) hh++;   
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k-j) / v * w)
                    tt --;
                q[++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1000010;

int a[N], q[N];

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

    int hh = 0, tt = -1;
    for (int i=0; i<n; i++) 
    {
        // 不用 while 是因为每一次只会扩展一个数字
        if (hh <= tt && i - k + 1 > q[hh]) hh ++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;

        if (i >= k-1) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i=0; i<n; i++) 
    {
        if (hh <= tt && i-k+1 > q[hh]) hh++;

        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    return 0;
}

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

const int N = 100010;

int stk[N], top, x, n;

int main()
{
    cin >> n;
    stk[++top] = -1;
    while (n --) {
        cin >> x;
        while (stk[top] >= x) top--;
        cout << stk[top] << " ";
        stk[++top] = x;
    }
    return 0;
}

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

const int N = 110, M = 25010;

int T, n, a[N];
long long f[M];

bool cmp(int a, int b) {    return a < b; }

int main()
{
    scanf("%d", &T);
    while (T--) 
    {
        scanf("%d", &n);
        int max_a = 0;
        for (int i=1; i<=n; i++){
            scanf("%d", &a[i]);
            max_a = max(max_a, a[i]);
        }
        sort(a+1, a+n+1, cmp);
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=a[i]; j<=max_a; j++) 
                f[j] += f[j-a[i]];
        }
        int ans = 0;
        for (int i=1; i<=n; i++)
            if (f[a[i]] == 1) ans++;
        cout << ans << endl;
    }
    return 0;
}

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110, M = 1010;
struct Edge{
    int u, v, w;
    bool operator < (const Edge &h) const {
        return w < h.w;
    }
}e[M];

int n, m, mst, fa[N], path[N];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x]; 
}

int main()
{
    freopen("graph.in", "r", stdin);
    freopen("mst.txt", "w", stdout);
    cin >> n >> m;
    for (int i=1; i<=m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e+1,e+m+1);

    int cnt = 0;
    for (int i=1; i<=n; i++) fa[i] = i;
    for (int i=1; i<=m; i++) {
        int pu = find(e[i].u), pv = find(e[i].v);
        if (pu != pv) {
            fa[pu] = pv;
            mst += e[i].w;
            path[++cnt] = i;
        }
        if (cnt == n-1) break;
    }
    if (cnt != n-1) cout << "No Solution!" << endl;
    else {
        for (int i=1; i<=cnt; i++) 
            printf("%d\t%d\t%d\n", e[path[i]].u, e[path[i]].v, e[path[i]].w);
    }
    return 0;   
} 

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

const int N = 20, M = 3010;

int n, m, v[N];
long long f[M];

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++) 
        cin >> v[i];
    f[0] = 1ll;
    for (int i=1; i<=n; i++) 
        for (int j=v[i]; j<=m; j++)
            f[j] += f[j-v[i]];
    cout << f[m] << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    for (int i=10; i<=n; i++) f[i] += f[i-10];
    for (int i=20; i<=n; i++) f[i] += f[i-20];
    for (int i=50; i<=n; i++) f[i] += f[i-50];
    for (int i=100; i<=n; i++) f[i] += f[i-100];
    cout << f[n] << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 110, M = 10010;
int n, m, f[M], v;

int main()
{
    cin >> n >> m;
    f[0] = 1;
    for (int i=1; i<=n; i++){
        cin >> v;
        for (int j=m-v; j>=0; j--) 
            if (f[j]) f[j+v] += f[j]; 
    }
    cout << f[m] << endl;
    return 0;
}

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

const int N = 1010, M = 510, K = 110;

int n, m, k, v1, v2, f[N][M];

int main()
{
    cin >> n >> m >> k;
    for (int i=1; i<=k; i++){
        cin >> v1 >> v2;
        for (int j=n; j>=v1; j--)
        for (int z=m-1; z>=v2; z--) 
            f[j][z] = max(f[j][z] , f[j-v1][z-v2] + 1);
    }

    int p = m - 1;
    while (p > 0 && f[n][p-1] == f[n][p]) p--;
    cout << f[n][m-1] << " " << m - p << endl;
    return 0;
}