Bzoj3749 [poi2015]łasuchy

DP也很妙妙啊pxp

阅读全文大概需要 4分钟
本文总阅读量
Posted by yjjr's blog on October 16, 2018

标签:DP

题目

题目传送门

Description

圆桌上摆放着n份食物,围成一圈,第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人,共有n个人。每个人有两种选择,吃自己左边或者右边的食物。如果两个人选择了同一份食物,这两个人会平分这份食物,每人获得一半的热量。 假如某个人改变自己的选择后(其他n-1个人的选择不变),可以使自己获得比原先更多的热量,那么这个人会不满意。 请你给每个人指定应该吃哪一份食物,使得所有人都能够满意。

Input

第一行一个整数n(2<=n<=1000000),表示食物的数量(即人数)。食物和人都从1~n编号。 第二行包含n个整数c[1],c[2],…,cn。 假设第i个人(1<=i<n)左边是第i份食物,右边是第i+1份食物;而第n个人左边是第n份食物,右边是第1份食物。

Output

如果不存在这样的方案,仅输出一行NIE。 如果存在这样的方案,输出一行共n个整数,第i个整数表示第i个人选择的食物的编号。如果有多组这样的方案,输出任意一个即可。

Sample Input

5
5 3 7 2 9

Sample Output

2 3 3 5 1

分析

\(f[i][j]\)表示第i个食物,状态为j时的方案数,\(j\in [1,4]\)

  • \(j=1\)表示食物被左边的人吃
  • \(j=2\)表示食物被右边的人吃
  • \(j=3\)表示食物不被人吃
  • \(j=4\)表示食物被左右两人同时吃掉

转移的时候要写很多不同的条件,有点烦,摔)

时间复杂度为\(O(n)\)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6;
int c[maxn],f[maxn][6],ans[maxn],n;
int main()
{
	n=read();
	rep(i,0,n-1)c[i]=read();c[n]=c[0];
	rep(i,1,4){
		mem(f,0);
		f[0][i]=1;
		rep(j,1,n){
			if(f[j-1][1]&&c[j]*2>=c[j-1])f[j][1]=1;
			if(f[j-1][1]&&c[j]>=c[j-1])f[j][4]=1;
			if(f[j-1][2]&&c[j-1]*2>=c[j])f[j][2]=2;
			if(f[j-1][2]&&c[j-1]>=c[j])f[j][3]=2;
			if(f[j-1][3]&&c[j]>=c[j-1])f[j][1]=3;
			if(f[j-1][3]&&c[j]>=c[j-1]*2)f[j][4]=3;
			if(f[j-1][4]&&c[j-1]>=c[j])f[j][2]=4;
			if(f[j-1][4]&&c[j-1]>=c[j]*2)f[j][3]=4;
		}
		if(!f[n][i])continue;
		for(int j=n,k=i;j>=1;j--){
			if(k==1||k==4)ans[j]=j%n+1;
			if(k==2||k==4)ans[j%n+1]=j%n+1;
			k=f[j][k];
		}
		rep(j,1,n)cout<<ans[j]<<' ';cout<<endl;
		return 0;
	}
	puts("NIE");
	return 0;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr