[bzoj 1863] [쪼이 2006] 트러블 황제의 고민(2점 정답+dp)

1863: [쪼이 2006] 트러블 황제의 고민

Time Limit: 1 Sec  
Memory Limit: 64 MB
Submit: 562  
Solved: 298
[ Submit][ Status][ Discuss]

Description

다년간의 살육을 거쳐 진황은 마침내 중국을 통일하였다.외래의 침략을 막기 위해 그는 국토 국경에 n명의 장군을 안치하려고 한다.불행하게도 이 n명의 장군은 날개가 점점 풍부해지면서 그들의 늑대 야심을 드러내기 시작했다.그들은 직무 진술을 거부하고 황제의 성지를 받아들이지 않았다.진황은 이 무례한 변방 대장들을 비밀리에 처단할 준비가 되어 있다.그러나 그는 병변을 막기 위해 먼저 이 장군들에게 훈장을 수여해 전략적 시간을 얻기로 했다.장군들은 곧 훈장이 수여된다는 말을 듣고 기뻐하며 잇달아 감사의 뜻을 표했다.i번째 장군은 서로 다른 색깔의 훈장을 받아 달라고 한다.그러나 이들 장군은 서로 인접한 두 장군이 같은 색깔의 훈장을 가지고 있다면 황제가 그들을 존중하지 않는다고 생각하고 즉각 반란을 일으킬 것이다(i번호 i의 장군과 i+1의 장군이 인접하고, 그들이 주둔하는 국경은 원형으로 볼 수 있기 때문에 번호 1과 번호 n의 장군도 인접한다).황제는 모든 장군들의 요구를 만족시켜야만 했지만, 그들의 제멋대로 날뛰는 것에 대해 매우 분노를 느꼈다.그래서 황제는 이 망령된 자들의 요구를 충족시키기 위해 가능한 한 적은 종류의 훈장을 주조하기로 결정했다.실례지만 그는 적어도 몇 가지 색깔의 훈장을 주조해야 합니까?

Input

첫 번째 줄에는 정수 n(1<=n<=20000)이 있다.다음 n행마다 하나의 정수ai는 i번째 장군이 몇 가지 훈장을 요구했는지 나타낸다.(1<=ai<=100000) 최소한 몇 종류의 훈장이 필요한지 정수를 출력합니다.

Output

4 2 2 1 1

Sample Input

4

Sample Output

HINT

Source

이분
[ Submit][ Status][ Discuss]
[문제풀이] [2점 정답+dp]
[우선 2분의 1로 답안을 나누고 가장 작은 훈장 수를 찾아 현재 값이 가능한지 dp로 판단한다]
[처음엔 전항을 총수에서 빼고 나머지는 현재를 지지하는 사람이 충분한 훈장을 받을 수 있을지 판단하는 것이 중요하다.]
[그러나 이렇게 발생하는 문제는 1과 충돌하면 배제할 수 없다는 것이다. 마지막으로 참고 문제: f[i]로 i개인이 전 사람과 충돌하지 않는 전제에서 1과 충돌하는 최대치를 나타낸다.g[i]는 제i개인이 전 사람과 충돌하지 않는 전제에서 1과 충돌하는 최소치를 나타낸다.마지막으로 현재 상황에서 최대 상황과 1이 충돌하는지 판단합니다.]
【방정식: g[i]=min(a[1]-f[i-1], a[i])f[i]=max(0, a[i]-(m-a[1]-a[i-1]+g[i-1])))]

#include
#include
#include
using namespace std;
int n,a[20010],f[20010],g[20010],maxn,sum,ans;
inline bool dp(int m)
{
	memset(g,0,sizeof(g));
	memset(f,0,sizeof(f)); 
    g[1]=f[1]=a[1];
    for(int i=2;i<=n;++i)
     {
     	g[i]=min(a[1]-f[i-1],a[i]);//  a[i-1]  ， a[1]       
     	f[i]=max(0,a[i]-(m-a[i-1]-a[1]+g[i-1]));//  a[i-1]  ， a[1]       
	 }
	return !f[n];
}
inline void qsort(int l,int r)
{
	int mid;
	while(l>1;
	 	if(dp(mid)) r=mid,ans=min(ans,mid);
	 	 else l=mid+1;
	 }
}
int main()
{
	int i,j,num;
	scanf("%d",&n);
	for(i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
	a[n+1]=a[1];
	for(i=1;i<=n;++i) 
	 if(maxn