Một bài quy hoạch động đơn giản cho beginer, trước hết tính mảng a[], sau đó dùng QHĐ, gọi f[i] là giá trị a[] lớn nhất từ 1 tới i. Dễ thấy f[i] = max(f[i-1], a[i]). Khi đó với mỗi test với giá trị n, ta chỉ cần in ra f[n].
Problem
https://vn.spoj.com/problems/MAXARR1
https://oj.vnoi.info/problem/MAXARR1
Năm ngoái Conan chỉ mới bước vào học Tin học thật sự. Thế nhưng anh ta bị đàn em là Như Quỳnh thách đố bài toán sau:
Cho T ≤ 100000. Mỗi dòng của T có 1 số N (N ≤ 100000). Dãy số A được xây dựng như sau:
- A[0] = 0
- A[1] = 1
- A[2i] = A[i]
- A[2i+1] = A[i] + A[i+1]
Nhiệm vụ của bạn là tìm số lớn nhất của dãy A từ 1 với N.
Input
Dòng đầu tiên là số T.
T dòng sau, mỗi dòng là 1 số N.
Output
Có T dòng tương ứng với giá trị lớn nhất của các đoạn.
Example
Input
2
5
10
Output
3
4
Tutorial
Submission
MAXARR1.cpp