1431. Diplomas
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
It might be interesting for you to learn that there are students who take part in various contests instead of studying. Sometimes such students are even awarded diplomas for winning these contests. Another amusing fact is that some deans collect and hang on the walls color copies of student diplomas. And when there are too many diplomas, extra walls are put up in a dean's office. But before a new wall is put up, its size should be determined, and for that a scheme of arranging diplomas on the wall is needed. That is why a designer is usually hired, to make everything beautiful.
A hired designer reckons that all diplomas of the same kind (for example, for winning semifinals) must be in the same row, and each row may contain diplomas of at most two different kinds. Moreover, if a row contains diplomas of two kinds, then they must alternate, and the last diploma in the row must be of the same kind as the first one for the sake of symmetry.
In order to determine how many walls should be put up, the dean has to know the minimal number of rows needed to arrange all the diplomas (the rows can be unboundedly long). Of course, having such clever students, it's not a big problem. That is to say, it is a problem, but a problem for the students.
Input
The first line of the input contains the number of different kinds of diplomas N (1 ≤ N ≤ 18). The second line contains the numbers of diplomas of each kind separated with a space: N integers in the range from 1 to 30.
Output
You should output the minimal number of rows needed to arrange the diplomas in accordance with the designer's requirements.
Sample
| input | output |
|---|---|
6 |
5 |
Problem Author: Stanislav Vasilyev
Problem Source: The 7th USU Open Personal Contest - February 25, 2006
Problem Source: The 7th USU Open Personal Contest - February 25, 2006
Tags: none (hide tags for unsolved problems)
Difficulty: 367
题意：问n样东西，每个东西都有一个值
1、每行最多放两样东西，可以放一样
2、如果两样东西放一行，则这两样东西的值必须差1
分析：n只有18，那岂不是怎么搞都行？
貌似可以贪心。。。
但我用了状压dp，显然的，每个位代表选了没有
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define Rep(i, t) for(int i = (0); i < (t); i++)
#define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
#define rep(i, x, t) for(int i = (x); i < (t); i++)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name)
{
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = ;
int n, Arr[N];
int Dp[N][ << N]; inline void Input()
{
scanf("%d", &n);
For(i, , n) scanf("%d", &Arr[i]);
} inline int Val(int x)
{
return << (x - );
} inline void Search(int x, int State, int Cnt)
{
if(Dp[x - ][State] <= Cnt) return;
Dp[x - ][State] = Cnt;
if(x > n) return ;
if(State & Val(x))
{
Search(x + , State, Cnt);
return;
}
Search(x + , State | Val(x), Cnt + );
For(i, x + , n)
if(!(State & Val(i)) && abs(Arr[i] - Arr[x]) == )
Search(x + , State | Val(x) | Val(i), Cnt + );
} inline void Solve()
{
clr(Dp, );
Search(, , );
cout << Dp[n][( << n) - ] << endl;
} int main()
{
#ifndef ONLINE_JUDGE
SetIO("A");
#endif
Input();
Solve();
return ;
}