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)); 
      } 
} 

을 그런데 : 난 당신의 코드를 수정하고 받아 가지고).