这两种写法的运行时间相差的可不是一点两点

/**
 * 第一种写法：
 *      状态表示：前i个精灵中，精灵球个数为j,攻击力总和为k的最大个数，
 *      状态计算：f[i][j][k] = max(f[i-1][j][k],f[i-1][j-v1][k-v2]+1)   之后就是将这个三维的优化成二维空间即可
**/
#include <iostream>

using namespace std;

const int N = 1010;
int n,m,kk,f[1010][510],v[N],w[N];

int main() {
    cin>>n>>m>>kk;
    for(int  i = 1;i <= kk;i++) {
        cin>>v[i]>>w[i];
    }

    // 前i个精灵中，精灵球个数为j,攻击力总和为k的最大个数，相同个数最少战斗力

    for(int i = 1;i <= kk;i++) {
        for(int j = n;j >= v[i];j--) {
            for(int k = m-1;k >= w[i];k--) {
                if(v[i] <= j && w[i] <= k) f[j][k] = max(f[j][k],f[j-v[i]][k-w[i]] + 1);
            }
        }
    }
    cout<<f[n][m-1];
    int k = m-1;
    while(k > 0 && f[n][m-1] == f[n][k-1]) k--;
    cout<<" "<<m-k<<endl;
    return 0;
} 

/**
 *  
 * 第二种写法：
 *      状态表示：所有前i个攻击力中，精灵个数不超过j的所有方案数；求使用最少精灵球的个数。
 *      状态计算：得到一个对应的精灵球个数，然后从大到小枚举精灵个数，从小到大枚举总攻击力。
**/

#include <bits/stdc++.h>

using namespace std;

const int N = 1010,inf = 0x3f3f3f3f;
int n,m,kk,f[510][110],v[N],w[N];

int main() {
    cin>>n>>m>>kk;
    for(int  i = 1;i <= kk;i++) {
        cin>>v[i]>>w[i];
    }

    // 所有前i个攻击力中，精灵个数不超过j的所有方案数；求使用最少精灵球的个数
    memset(f,inf,sizeof f);
    f[0][0] = 0;
    for(int i = 1;i <= kk;i++) {
        for(int j = m;j >= w[i];j--) {
            for(int k = kk;k >= 1;k--) {
                if(f[j-w[i]][k-1] + v[i] <= n) f[j][k] = min(f[j][k],f[j-w[i]][k-1] + v[i]);
            }
        }
    }
    // 个数从大到小开始枚举，因为题目要求个数尽量大，总的攻击力尽量小。
    for(int k = kk;k>=0;k--) {
        int p = inf;
        // 所以 总攻击力就是从小到大枚举
        for(int j = 0;j < m;j++) {
            if(f[j][k] != inf && j < p) {
                p = j;
            }   
        }
        if(p != inf) {
            cout<<k<<" "<<m-p<<endl;
            return 0;
        }
    }

    return 0;
}