2015-01-06 51 views
1

我目前正在學習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。我知道我在程序中犯了一些愚蠢的錯誤,但一段時間以來一直試圖找到它,其他人能幫我找出錯誤嗎?

+0

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

+0

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

回答

3

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

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

+0

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