UVA 1073 Glenbow Museum

https://vjudge.net/problem/UVA-1073

题目

对于一个边平行于坐标轴的多边形,我们可以用一个由R和O组成的序列来描述它:从某个顶点开始按照逆时针顺序走,碰到一个90°的内角(也就是左转)记R;碰到一个270°的内角(右转)记O。这样的序列称为角度序列。由于没有指定边长,所以边长任意。

现在给定正整数L,求有多少个长度为L的角度序列至少可以对应一个星型多边形(即多边形中存在一个点可以看到多边形边界上的每一个点)。

注意,一个多边形有多条序列与之对应,比如RRORRORRORRO=RORRORRORROR=ORRORRORRORR

$1\leqslant L\leqslant 1000$

题解

题目的条件可以推出R比O多4个,$\Rightarrow$:首先摆好4个R,然后剩下的边方向都不变,$\Leftarrow$:从完成的部分可以选出4个R,然后剩下的方向都不变。

由于是星形,不能出现OO

设$dp[l][\Delta][s][t]$为长度为$l$,开始为$s$,结束为$t$,$R-O=\Delta$的序列个数

答案是$dp[L][4][R][R]+dp[L][4][R][O]+dp[L][4][O][R]$,因为[O][O]会导致方向改变。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define REPE(i,a,b) for(int i=(a); i<=(b); i++)
#define PERE(i,a,b) for(int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
ll dp[1007][7][2][2]; //-1 0 1 2 3 4 5
int main() {
	memset(dp,0,sizeof dp);
	dp[1][2][1][1]=1; //r-o
	dp[1][0][0][0]=1;

	REPE(l,2,1000) {
		dp[l][0][0][0]=dp[l-1][1][0][1];
		dp[l][0][1][0]=dp[l-1][1][1][1];
		REP(i,1,6) {
			dp[l][i][0][0]=dp[l-1][i+1][0][1];
			dp[l][i][0][1]=dp[l-1][i-1][0][0]+dp[l-1][i-1][0][1];
			dp[l][i][1][0]=dp[l-1][i+1][1][1];
			dp[l][i][1][1]=dp[l-1][i-1][1][0]+dp[l-1][i-1][1][1];
		}
		dp[l][6][0][1]=dp[l-1][5][0][0]+dp[l-1][5][0][1];
		dp[l][6][1][1]=dp[l-1][5][1][0]+dp[l-1][5][1][1];

	}
	int L, kase=0;
	while(~scanf("%d", &L) && L) {
		printf("Case %d: ", ++kase);
		if((L&1) || L<4) {
			puts("0");
			continue;
		}
		ll ans=dp[L][5][0][1]+dp[L][5][1][0]+dp[L][5][1][1];
		printf("%lld\n", ans);
	}
}

 

上一篇:例题7-6(uva-140)


下一篇:UVA - 1393 Highways (和紫书不一样的解法)