1079-C 贪心orDP我选择DP

https://codeforces.com/contest/1079/problem/C

题目很简单

给一个1e5长的数组a(a[i]∈[1,1e5])

求一个任意同等长度数组b

使

有则输出，不存在输出-1

刚开始想到，在怎样的情况下存在b数组,b数组应该是怎丫的

，结果。。。。

贪心快一个小时还没贪出来，总是有考虑不到的情况

后来补题的时候，发现这题1e5*5*5，完全可以dp搜索。。。

结论:可以用dp就绝不用贪心，不能贪，管住手

最后还是附一个补题时5分钟打出来的代码吧(跟1小时还打不出的贪心差别太大了)

//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
typedef long long ll;
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e5+5);
int a[maxn], b[maxn];
int dp[maxn][7];
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), times(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++times, T--)
	{
		int n; cin >> n;
		RE2(i, n)cin >> a[i];
		RE2(i, 5)dp[1][i] = 1;
		F(i, 1, n - 1)
		{
			RE2(j, 5)
			{
				if (dp[i][j])
				{
					RE2(k, 5)
					{
						bool ok(0);
						if (a[i] < a[i + 1] && j < k)ok = 1;
						if (a[i] > a[i + 1] && j > k)ok = 1;
						if (a[i] == a[i + 1] && j != k)ok = 1;
						if (ok)dp[i + 1][k] = 1;
					}
				}
			}
		}
		int las(0);
		RE2(i, 5)if (dp[n][i]) {
			las = i; b[n] = las; break;
		}

		if (las == 0)
		{
			cout << -1 << endl; break;
		}
		F2(i, n - 1, 1)
		{
			int k = b[i + 1];
			RE2(j, 5)if(dp[i][j])
			{
				bool ok(0);
				if (a[i] < a[i + 1] && j < k)ok = 1;
				if (a[i] > a[i + 1] && j > k)ok = 1;
				if (a[i] == a[i + 1] && j != k)ok = 1;
				if (ok)
				{
					b[i] = j; break;
				}
			}
		}
		RE2(i, n)
		{
			if (i != 1)cout << ' ';
			cout << b[i];
		}
		cout << endl;


	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}