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
。我知道我在程序中犯了一些愚蠢的錯誤,但一段時間以來一直試圖找到它,其他人能幫我找出錯誤嗎?
程序中最大的問題是它沒有評論。這對於編程競賽來說很好,但是當你把它提交給像這樣的論壇尋求幫助和建議時不會。 – TonyK
@TonyK Ya,我知道,這是我最大的弱點之一,非常抱歉,我的競爭意識非常強烈,但我有時覺得在代碼中添加註釋會破壞工作流程,有時會導致代碼混亂......此外,我正在爲INOI準備這些天,因此我的工作重點完全在於algorirhms,而不是代碼之美。 –