BZOJ 3749 Łasuchy

发表于 | 更新于

Link

想到了DP，也想出了状态，也想出了转移，但想不出怎么设置初始值。。

Solution

注意：平分不取整。。 f[i][0/1][0/1]f[i][0/1][0/1]表示第ii个和第i+1i+1个人分别选他左/右的食物，能否让前ii个人满意。 转移就很显然了。 然而因为是个环，初始状态怎么设置？ 没有办法，只好取Orz Claris大神，被深深折服了： 依次枚举f[1][0/1][0/1]f[1][0/1][0/1]每一维状态成立，DP完之后看能否满足 这就类似反证法的思路了吧。。假设结论成立，推矛盾。感觉非常地厉害！ 我在实现的时候把第n+1n+1个当成第11个，这样只要DP完了，看是否f[n+1][S]==1f[n+1][S]==1即可。

Tips

这种假设成立，带进去跑的做法比较厉害啊，，有点像 的感觉啊，又有点二分答案的感觉啊。。。 好吧，虽说这种枚举答案的做法也不是很少见，但我还是第一次见到放在这一类问题里面。可以记住这个脑洞啊

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "lucida"
const int MAXN=1000000+11;
bool f[MAXN][4];
int c[MAXN],n,pre[MAXN][4],last;
bool DP(int s) {
	memset(f,0,sizeof(f));
	memset(pre,0,sizeof(pre));
	f[1][s]=1;c[n+1]=c[1],c[n+2]=c[2];
	for(int i=2;i<=n+1;++i)
		for(int cs=0;cs<4;++cs)
			for(int ps=0;!f[i][cs] && ps<4;++ps)
				if(f[i-1][ps] && ((ps&1)==(cs>>1&1))) {
					int lchs=(ps>>1&1),chs=(ps&1),rchs=(cs&1),valc,valo;
					if(chs==1) {
						valc=rchs==0?c[i+1]:c[i+1]*2;
						valo=lchs==1?c[i]:c[i]*2;
					} else {
						valc=lchs==1?c[i]:c[i]*2;
						valo=rchs==0?c[i+1]:c[i+1]*2;
					}
					f[i][cs]=valc>=valo;
					pre[i][cs]=ps;
				}
	last=pre[n+1][s];
	return f[n+1][s];
}
int main() {
//	freopen("input","r",stdin);
	is>>n;
	for(int i=1;i<=n;++i)
		is>>c[i];
	bool nie=1;
	for(int s=0;s<4;++s)
		if(DP(s)) {
			nie=0;
			break;
		}
	if(nie)
		os<<"NIE"<<'\n';
	else {
		static int seq[MAXN];
		for(int i=n;i>=1;--i) {
			seq[i]=(last>>1&1);
			last=pre[i][last];
		}
		for(int i=1;i<=n;++i) { 
			seq[i]=seq[i]==0?i:(i==n?1:i+1);
			os<<seq[i]<<(i==n?'\n':' ');
		}
	}
	return 0;
}