鋸齒形序列[動態規劃]錯誤

我目前正在學習DP和我通過topsider教程學習，並試圖解決的問題和了解，並知道解決辦法是非常相似的計算長度去最長增加子序列。我編程的簡單的C++ DP的解決方案如下：鋸齒形序列[動態規劃]錯誤

#include <iostream> 
#include <vector> 
using namespace std; 

int main(void) 
{ 
    int n = 50; 
    int numbers[] =   
{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }; 
    vector<int> length(n, 1); 
    for(int i = 1;i < n;i++) 
    { 
     for(int j = (i - 1);j >= 0;j--) 
     { 
      if(length[j] + 1 > length[i]) 
      { 
       if(length[j] % 2 == 0) 
       { 
        if(numbers[i] - numbers[j] < 0) 
        { 
         length[i] = length[j] + 1; 
        } 
       } 
       else 
       { 
        if(numbers[i] - numbers[j] > 0) 
        { 
         length[i] = length[j] + 1; 
        } 
       } 
      } 
     } 
    } 
    printf("%d\n", *(max_element(length.begin(), length.end()))); 
}

但問題是代碼正常工作對所有其他情況下，除了這一個：

{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

我的代碼打印答案35而topsider相信它的36。我知道我在程序中犯了一些愚蠢的錯誤，但一段時間以來一直試圖找到它，其他人能幫我找出錯誤嗎？

來源

2015-01-06 Nalin Bhardwaj

程序中最大的問題是它沒有評論。這對於編程競賽來說很好，但是當你把它提交給像這樣的論壇尋求幫助和建議時不會。 – TonyK

@TonyK Ya，我知道，這是我最大的弱點之一，非常抱歉，我的競爭意識非常強烈，但我有時覺得在代碼中添加註釋會破壞工作流程，有時會導致代碼混亂......此外，我正在爲INOI準備這些天，因此我的工作重點完全在於algorirhms，而不是代碼之美。 –

我懷疑的問題是，第一差可以是正的或負的，但你的代碼只支持其中一個案件。

也許你應該積極的，然後再第二次負第一兩次運行此代碼，一次。

來源

2015-01-06 18:34:09

嗯，錯誤地假設了...... :) –

鋸齒形序列[動態規劃]錯誤

回答

相關問題