c++ - 当我尝试提交 mkbudget spoj 时得到 WA

Question

我无法理解/想到我的代码无法给出正确输出的情况。问题链接:http://www.spoj.pl/problems/MKBUDGET/

问题显然有 DP 解决方案。我在下面发布我的解决方案:

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector <int> > opt;

void compute_opt(vector<int> A,int n,int hire,int fire,int sal,int max_a)
{
    for(int i = A[0]; i <= max_a; i++)  //for num workers in 1st month
        opt[0][i] = i*(hire + sal);

    for(int i = 1; i < n; i++)  //num of months
        for(int j = A[i]; j <= max_a; j++)  //num of workers for ith month >=A[i] and <= max_a
            {
                opt[i][j] = opt[i-1][A[i-1]] + j*sal + (A[i] > A[i-1] ? (A[i]-A[i-1])*hire : (A[i-1] - A[i])*fire);

                for(int k = A[i-1]; k <= max_a; k++)
                    opt[i][j] = min(opt[i][j], opt[i-1][k] + j*sal + (j>k ? (j-k)*hire : (k-j)*fire));
            }   
}

int ans(vector<int> A, int n, int max_a)
{
    int ret = opt[n-1][A[n-1]];
    for(int i = A[n-1]; i <= max_a; i++)
        ret = min (ret, opt[n-1][i]);

    return ret; 
}

int main()
{
    vector<int> A;
    int n, hire, fire, sal,max_a, c = 1;
    while(1)
    {
        cin >> n;
        if(n == 0)
            break;

        A.clear();
        opt.clear();
        max_a = 0;
        cin >> hire >> sal >> fire;
        A.resize(n);
        for(int i = 0; i < n; i++)  
            {cin >> A[i];
             max_a = max(max_a,A[i]);
             }

        opt.resize(n);  
        for(int i = 0; i < n; i++)
            opt[i].resize(max_a + 2);

        compute_opt(A,n,hire,fire,sal,max_a);
        cout << "Case " << c << ", cost = $" << ans(A,n,max_a) << endl;
        c++;
    }
    return 0;
}

我得到了两个示例测试用例的正确答案，但在提交时得到了 WA。有什么帮助吗？

Answer 1

好的，所以您的问题是您不允许在 A[i] 和 A[i - 1] 之间雇用任意数量的员工。也许解雇一些不需要的员工是个好主意，但不是全部。这就是你得到 WA 的原因。我修改了您的代码并接受了它:

void compute_opt(vector<int> A,int n,int hire,int fire,int sal,int max_a)
{
    // Fill all disallowed entries with infinity
    for (int i = 0; i < A[0]; ++i)
        opt[0][i] = 1000000000;
    for(int i = A[0]; i <= max_a; i++)  //for num workers in 1st month
        opt[0][i] = i*(hire + sal);

    for(int i = 1; i < n; i++)
        for(int j = 0; j <= max_a; j++)
            {
                // No need for special case handling,
                //just check all previous numbers of employees
                opt[i][j] = 1000000000;
                if (A[i] > j) continue;
                for(int k = 0; k <= max_a; k++)
                    opt[i][j] = min(opt[i][j],
                       opt[i-1][k] + j*sal + (j>k ? (j-k)*hire : (k-j)*fire));
            }   
}

顺便说一句，有一个比您拥有的解决方案“更贪婪”的解决方案，它不依赖于较小的员工数量(以便可以分配 table )。