Trợ giúp trong vấn đề DP

Question

Tôi đang cố gắng giải quyết vấn đề từ SPOJ (link), có thể được mô tả ngắn gọn như sau: Cho khoảng thời gian n, mỗi khoảng có số nguyên bắt đầu và kết thúc, và kết thúc bằng thời gian tối đa (hãy gọi nó là max_end), tìm xem bạn có thể chọn bao nhiêu khoảng thời gian bao gồm 1 ... max_end. Khoảng thời gian có thể chồng lên nhau. Tôi đã thử một DP; lần đầu tiên sắp xếp theo thời gian kết thúc, sau đó dp [i] là một cặp, trong đó dp [i] .đầu tiên là số khoảng thời gian tối thiểu cần thiết để bao gồm 1 ... kết thúc [i] lần sử dụng cuối cùng i và dp [i] .second là số cách để làm điều đó. Đây là vòng DP chính của tôi:

for(int i = 1; i < n; i ++) { 
    for(int j = 0; j < i; j ++) { 
     if(! (x[ j ].end >= x[ i ].start - 1)) 
      continue; 
     if(dp[ j ].first + 1 < dp[ i ].first) { 
      dp[ i ].first = dp[ j ].first + 1; 
      dp[ i ].second = dp[ j ].second; 
     } 
     else if(dp[ j ].first + 1 == dp[ i ].first) { 
      dp[ i ].second += dp[ j ].second; 
     } 
    } 
} 

Thật không may, nó không hoạt động. Ai đó có thể cho tôi biết tôi có sai sót không? Cảm ơn trước! :)

Answer 1

Tôi không chắc tôi có được ý tưởng giải pháp của bạn, nhưng tôi mô tả giải pháp AC của tôi:

Tôi đang sử dụng chức năng với ghi nhớ, nhưng bạn có thể viết lại nó bằng cách sử phi recurcive DP.

Giả sử chúng tôi có khoảng thời gian của chúng tôi trong mảng

ghép nối [100]; trong đó một [i] .đầu tiên là khoảng bắt đầu và [i] .second là khoảng thời gian kết thúc.

Sắp xếp mảng này theo bắt đầu trước (hành vi mặc định của thuật toán sắp xếp stl với bộ so sánh cặp mặc định).

Bây giờ hãy tưởng tượng rằng chúng tôi đang "đặt" từng khoảng một từ đầu đến cuối.

cho f (int x, int prev) trả về số cách để hoàn tất quá trình điền nếu khoảng thời gian hiện tại cuối cùng là x và trước đó là 'trước'.

chúng tôi sẽ tính toán nó như sau:

int f(int x, int prev) { 
    // if already calculated dp[x][prev], return it. Otherwise, calculate it 
    if (dp[x][prev] != -1) { 
    return dp[x][prev]; 
    } 
    if (a[x].second == m) { 
    return dp[x][prev] = 1; // it means - X is last interval in day 
    } 
    else { 
    dp[x][prev] = 0; 
    for (int i = x + 1; i < n; ++i) { // try to select next interval 
     if (a[i].first <= a[x].second && // there must be not empty space after x interval 
      a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless 
      a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless 
      a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless. 
     dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000; 
     } 
    } 
    } 
    return dp[x][prev]; 
} 

Sau đó chúng ta cần phải gọi hàm này cho mỗi cặp khoảng, lần đầu tiên trong số đó bắt đầu từ 0 và thứ hai được kết nối với đầu tiên:

for (int i = 0; i < n; ++i) { 
    if (a[i].first == 0) { 
    for (int j = i + 1; j < n; ++j) { 
     if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless 
      a[j].first <= a[i].second && // there must be no space after i interval 
      a[j].second > a[i].second) { // in opposite case j will be useless 
      res = (res + f(j, i)) % 100000000; 
     } 
    } 
    // also we need to check the case when we use only one interval: 
    if (a[i].second == m) { 
     res = (res + 1) % 100000000; 
    } 
    } 
} 

Sau đó, chúng tôi chỉ cần in bản in.