Giup mình giai bai nay voi
Trong kỳ thi học sinh giỏi môn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i có giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy.
Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất.
Dữ liệu vào: cho file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N
- N dòng tiếp theo lần lượt là giá trị của các phần thưởng.
Dữ liệu ra: ghi ra file PTHUONG.OUT gồm các dòng:
- Dòng đầu tiên ghi tổng giá trị lớn nhất của các phần thưởng đã chọn
- Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự tăng dần
pthuong.inp
7
6 9 1 3 5 10 4
pthuong.out
32
1 2 4 6 7
Mình giải bằng C++ nha bạn
#include<cstdio>
#include<cstdlib>
const int N=1e4+1;
int f[N], f0[N], f1[N], f2[N], a[N];
int t[N], t0[N], res[N];
void m3(int &x, int &y, int a, int b, int c) {
x=a;
if (b>x) x=b;
if (c>x) x=c;
if (x==a) y=0;
else if (x==b) y=1;
else y=2;
}
void m4(int &x, int &y, int a, int b, int c, int d) {
m3(x,y,a,b,c);
if (d>x) { x=d; y=3; }
}
void quit(int x) {
printf("%d",x);
exit(EXIT_SUCCESS);
}
int main()
{
freopen("PTHUONG.INP", "r", stdin);
freopen("PTHUONG.OUT", "w", stdout);
int n, i, j=3, m=0;
scanf("%d",&n);
for (i=1; i<=n; i++) scanf("%d",a+i);
if (!n) quit(0);
if (n==1) quit(a[1]);
f1[1]=a[1];
m3(f[1],t[1], f0[1],f1[1],f2[1]);
for (i=2; i<=n; i++)
{
m3(f0[i],t0[i], f0[i-1],f1[i-1],f2[i-1]);
f1[i]=f0[i-1]+a[i];
f2[i]=f1[i-1]+a[i];
m4(f[i],t[i], f0[i],f1[i],f2[i],f[i-1]);
}
printf("%d\n",f[n]);
i=n;
while (i) {
if (j==3) {
if (t[i]!=3) j=t[i];
else i--;
}
else if (j>0) {
res[++m]=i--;
j--;
}
else {
j=t0[i];
i--;
}
}
for (i=m; i>0; i--) printf("%d ", res[i]);
return 0;
}
