Glenbow Museum
首先要发现一些性质:
- 不能出现双O
- 有且仅有四次双R出现(首尾相连也算)
- R数刚好多O数四个
- R数和O数相加等于总长
关于发现方法，可以考虑先放一个只有4*R的矩形进去，然后添加拐角(OR)，这样不难发现如上性质。
那么这道题就好许多的。
R的数目为 \((n+4)/2\) , O的数目为 \((n-4)/2\) 。
现在还需要发现一个性质：只要R比O多4个，随意组合都为可行解。
可以这么理解：双R表示一次转角，那么对于原矩形，本来就要转4次角。所以只要R多了四个，必定就有4次双R。
设计DP
令 \(dp(i,j,k)\) 表示有 \(i\) 个R，\(j\) 个双R，初始字符为 \(k(1为O,0为R)\) ，末字符为R的方案数。
边界为：\(dp(1,0,0)=1(R),dp(1,0,1)=1(OR)\)
那么有如下转移方程：\(dp(i,j,k)=dp(i-1,j,k)+dp(i-1,j-1,k)*(j!=0)\)
最终结果呢？
\(ans(i)=dp((i+4)/2,4,1)+dp((i+4)/2,4,0)+dp((i+4)/2,3,0)\)
其中第二项表示R开头O结尾的串数，尽管设计的时候默认最后一个元素是R，但是添不添O对方程本身并不影响，所以可以用此计算这种情况。
const int N=510,L=1010;
int n;
ll f[N][N][2],ans[L];
//i个R,j个相邻R,第一位为k,结尾为R,且无相邻O的方案数
inline void Pre(){
f[1][0][1]=f[1][0][0]=1;//OR,R
for(int i=2;i<=505;++i)
for(int j=0;j<=4;++j){
for(int k=0;k<=1;++k){
f[i][j][k]=f[i-1][j][k];
if(j) f[i][j][k]+=f[i-1][j-1][k];
}
}
for(int i=4;i<=1000;++i) if(i%2==0){
ans[i]=f[(i+4)/2][4][1]+f[(i+4)/2][3][0]+f[(i+4)/2][4][0]/*R开头O结尾*/;
}
}
signed main(){
Pre();
int kase=0;
while(scanf("%d",&n)&&n){
printf("Case %d: %lld\n",++kase,ans[n]);
//初始为矩形-->4*R,添加拐角(1*O+1*R)
//所以最后一定有n(O)+4=n(R),n(O)+n(R)=l
//且理应出现四次RR,不允许O连续出现,即其余都为RORO...
}
return 0;
}
· EOF
标签：P2,UVA1073,int,Museum,dp,Glenbow From： https://www.cnblogs.com/mfc007/p/17643619.html