背包DPWA求助
查看原帖
背包DPWA求助
833124
BIOS楼主2024/3/25 19:43
#include <iostream>
#include <cstring>
using namespace std;
const int N = 201;
int f[N][N][N], n, m, t, v, w[N], top;
string line;
int main()
{
    int tot;
    cin >> tot;
    while (tot--)
    {
        cin >> n >> t >> m, memset(f, 0, sizeof(f));
        getline(cin, line), getline(cin, line), top = 0;
        for (int i = 0; i < line.size(); i++)
        {
            int p = i, x = 0;
            while (line[i] >= '0' && line[i] <= '9')
                x = x * 10 + line[i] - '0', i++;
            w[++top] = x, i++;
        }
        for (int i = 1; i <= n; i++)
        {
            v = w[i];
            for (int j = 1; j <= m; j++)
                for (int k = 0; k <= t; k++)
                {
                    f[i][j][k] = f[i - 1][j][k];
                    if (k >= v)
                        f[i][j][k] = max(f[i][j][k], max(f[i - 1][j - 1][t], f[i - 1][j][k - v]) + 1);
                }
        }
        cout << f[n][m][t] << "\n";
        if (tot)
            cout << "\n";
    }
}

Udebug的两个数据都过了,N=205是我自己猜的数据范围,因为开101RE了。从双倍经验题来的,那个题A了这个题WA

2024/3/25 19:43
加载中...