30/09/2018, 16:01
Bài toán quy hoạch động
Ae nào đọc qua về quy hoạch động xem hộ e xem đoạn code này e sai chỗ nào với …đề là : tìm dãy con dài nhất trong mảng sau … 5,2,3,4,9,10,5,6,7,8… đáp án là 2,3,4,5,6,7,8
#include <iostream>
using namespace std;
int mang[11];
int length[100];
int trance[100];
int main()
{
length[10] = 1;
mang[0] = -32768;
mang[10] = 32767;
for (int i = 1;i<10;i++)
{
cout << "mang[" << i << "] = " ;
cin >> mang[i];
cout << endl;
}
for (int i = 9;i>=0;i--)
{
if (mang[i] <= mang[i+1])
{
length[i] = length[i+1] + 1;
trance[i] = i;
}
else
{
length[i] = 0;
for (int j = i+1;j<11;j++)
{
if(mang[j] > mang[i]&&length[j]>length[i])
{
length[i] = length[j] + 1;
trance[i] = j;
}
}
}
}
int duyet = 0;
while(duyet != 10)
{
duyet = trance[duyet];
cout << mang[duyet];
}
system("pause");
return 0;
}
Bài liên quan
