當我嘗試提交mkbudget虛假代碼時獲取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)); 
      } 
} 

順便說一句，有一個「貪婪」的解決方案比你有不依賴於員工是小（數量，以使表可以分配一個）。