Nizamovoff
@Nizamovoff
Программист на С++

Как решить задачу на динамическое программирование?

Помогите, пожалуйста, решить задачу. Код есть, но не понимаю, в чем ошибка. WA10

Задача:5f835e472c718897267650.png

Код:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define ff first
#define ss second
#define ep(x) emplace_back(x)
#define mp(x, y) make_pair(x, y)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<int> ans;
	vector<pair<pii, bool>> mas(n);
	for (int i = 0; i < n; i++) { cin >> mas[i].ff.ff; mas[i].ff.ss = i + 1; }
	int l = mas[0].ff.ff, r = mas[n - 1].ff.ff;
	mas[0].ss = mas[n - 1].ss = 1;
	for (int i = 1; i < n - 1; i++) {
		if (mas[i].ff.ff >= l && mas[i].ff.ff <= r && mas[i].ff.ff >= mas[i - 1].ff.ff && mas[i].ff.ff <= mas[i + 1].ff.ff) mas[i].ss = 1;
		else mas[i].ss = 0;
	}
	for (int l = 0; l <= 200; l++) {
		for (int i = 1; i < mas.size() - 1; i) {
			if (mas[i].ss == 0) {
				if (mas[i].ff.ff > mas[i - 1].ff.ff && mas[i].ff.ff > mas[i + 1].ff.ff) { ans.ep(mas[i].ff.ss); mas.erase(mas.begin() + i); }
				else if (mas[i].ff.ff < mas[i - 1].ff.ff && mas[i].ff.ff < mas[i + 1].ff.ff) { ans.ep(mas[i].ff.ss); mas.erase(mas.begin() + i); }
				else i++;
			}
			else i++;
		}
	}
	for (int i = 1; i < mas.size(); i++) if (mas[i].ff.ff < mas[i - 1].ff.ff) { cout << -1; return 0; }
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}


Спасибо за помощь!
  • Вопрос задан
  • 146 просмотров
Решения вопроса 1
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Программа явно лажает, например для входных данных
4
6 10 5 20

очевидный ответ -- срубить третий дуб, но программа выводит
2
2 3


pair<pii, bool>

Использование структуры с разумными названиями полей вместо этого существенно бы облегчило чтение кода.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
SagePtr
@SagePtr
Еда - это святое
Если задача на динамическое программирование - то тут всё просто, составьте динамическую таблицу на бумаге, затем ту же таблицу посчитайте в программе и выведите на экран, и сравните их, что где не так считает.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы