T3:DP(基于排列组合思想的状态转移)

其实之前写排列组合的题目有一种很茫然的感觉....

应该是因为之前没有刷过所以没有什么体会

上次刷的vj1060有用到,但是写状态转移还是第一次学习吧

ccy大神的题解如果认真去思考的话很容易看懂...感觉他写得太详细了,以至于自己都不想自己敲题解了

附上代码和注释再说说自己的感受吧:

1先判断出这个序列是否可行,不可行就输出无解,若可行那么做步骤2,3计算。

2递推出有i个灯时的所有状态数(无论可行不可行)状态表示:f[i,j,k]:表示i个灯,绿,红灯的奇偶性为j,k时的所有状态数。奇为0,偶为1
f[i,0,0] = f[i-1,1,0]+f[i-1,0,1]+f[i-1,0,0];
f[i,0,1] = f[i-1,1,1]+f[i-1,0,0]+f[i-1,0,1];
以此类推.......(不要害怕我会给大家详细解释)
3根据现有的序列按字典序累加答案。 然后我给大家解释一下吧
其状态可以说是明白的
f[i,j,k]就和他说的那样表示i个灯,j表示绿灯的个数的奇偶性,k是红灯的个数的奇偶性
(其中0 表示x灯的个数为奇数,1表示x灯的个数为偶数)
大家不要着急看程序:看我给诸位推一推边界(这些都是很有用的);
先讨论一个灯的时候
我们有
f[1,0,0]=0;表示灯的个数为1,绿灯的个数为奇数,红灯的个数也为奇数的状态,当然这是可能的,因为有了一个绿灯那么另外一个就不是奇数了,也就是说无论如何都不可能在1的时候出现这种情况,所以赋值为0表示这种情况的方案数为0
f[1,1,0]=1;表示灯的个数为1,绿灯的个数为偶数,红灯的个数为奇数,这时候有一种情况就是一个灯,而这个灯是红灯(奇数),这时绿灯的个数为0(奇数);
f[1,0,1]=1;表示灯的个数为1,绿灯的个数为奇数,红灯的个数为偶数,这时候有一种情况就是绿灯有一个(奇数),红灯为0(偶数);
f[1,1,1]=1;表示灯的个数为1,绿灯的个数为偶数,红灯的个数为偶数,这时候有一种情况就是这灯是黄色的;这样红灯和绿灯的个数都为0(偶数) 接下来开始讨论两个灯的时候
首先按照方程的第一和第二行,我们有
f[2,0,0]:=f[1,1,0]+f[1,0,1]+f[1,0,0] ······④
即两个灯,绿灯的个数为奇数,红灯的个数为奇数的方案数
其会等于一个灯的情况:(我按照顺序给出一个灯的情况)
①Red即f[1,1,0]要达到f[2,0,0]只需要变成Red,Red即可即两个红灯
②Green即f[1,0,1]要达到f[2,0,0]只需要变成green,green即可即两个绿灯
③这个起到的是递推作用,虽然现在f[1,0,0]是0,但是f[2,0,0]明细不是0了
那么假如我们现在是在推第3个那么f[3,0,0]:=f[2,1,0]+f[2,0,1]+f[2,0,0]的情况了这个时候f[2,0,0]是两个等都是奇数的情况,
此时加上一个yellow就变成f[3,0,0]了而且也只能这样,这样就更证明了方程的正确性,对于前面的①和②也是如此,都可以证明这种状态只能从那种状态转移过来
剩下的三个方程将在程序中给出,其方程都可以由自己推出;
目的是为了将f[2,0,1],f[2,1,0],f[2,1,1]都得推出来。以及f[n,....] 好了我们切入算法部分
初始时ans:=1;//我们要找的是比它的序列先的序列.所以找到的序列数应该加一
对于样例
RGYR
我们要从字典序出发G->R->Y;
好的
R前面有G
那么我们转化成
R???的形式
很显然我们要加入一个灯数为3的xxx(未知排列)
这个排列应该满足整个序列仍然满足绿奇、红偶.
那么ans就应该加上f[3,0,0]表示加入一个绿灯为奇数的,红灯为奇数的序列(长度为3)
因为序列中已知部分只有R一个(R是奇数,但是其要偶数,红偶);所以要加上一个奇数(奇数+奇数=偶数)
而已知部分中G为0个,所以要加上一个奇数(偶数+奇数=奇数,绿奇);
然后G就没有了,它的下一个就是R了
然后是RG???,对于G来说它的字典序是最小的所以跳过
然后是RGY?,对于Y来说它的字典序前面还有R和G
那么先讨论G的情况(当然这两个情况可以同时讨论)
RGG?->因为G(绿)为偶数,而绿要奇数,所以加上f[1,0,y],y是什么呢?相信大家都会了,思考一下吧
然后是
RGR?->因为这是G是奇数所以加上偶数,即加上f[1,1,y],y还是由读者思考
var
i,j,n,a,b,g,r:longint;
ans:int64;
f:array[0..100001,0..1,0..1]of longint;
s:ansistring; procedure go_1;
begin
g:=g+1;
if (odd(g)) and (not odd(r)) then//根据g和r的奇偶性处理相应问题
ans:=(ans+f[n-i,1,1]) mod 12345;
if (odd(g)) and (odd(r)) then
ans:=(ans+f[n-i,1,0]) mod 12345;
if (not odd(g)) and (not odd(r)) then
ans:=(ans+f[n-i,0,1]) mod 12345;
if (not odd(g)) and (odd(r)) then
ans:=(ans+f[n-i,0,0]) mod 12345;
g:=g-1;//用完g后要注意删掉
end; begin
readln(n);
readln(s);
fillchar(f,sizeof(f),0);
f[1,0,1]:=1;
f[1,1,1]:=1;
f[1,1,0]:=1;
f[1,0,0]:=0;
for i:=2 to n do
begin
f[i,0,0]:=(f[i-1,0,0]+f[i-1,0,1]+f[i-1,1,0])mod 12345;
f[i,0,1]:=(f[i-1,0,1]+f[i-1,1,1]+f[i-1,0,0])mod 12345;
f[i,1,0]:=(f[i-1,0,0]+f[i-1,1,0]+f[i-1,1,1])mod 12345;
f[i,1,1]:=(f[i-1,1,1]+f[i-1,1,0]+f[i-1,0,1])mod 12345;//这是另外4个递推式 要注意mod
end;
ans:=1;//一开始ans=1具体为什么我上面有解释
g:=0;r:=0;
for i:=1 to n do
case s[i] of
'G':inc(g);//字典序是最小的了所以不需要处理,直接增加g的数目
'R':begin
go_1;//go_1是处理G的情况 因为R前面的字典序只有一个所以只要处理一个
inc(r);//r的数目加1
end;
'Y':begin
go_1;//先处理G的情况 因为Y的字典序前面有G,R,所以还要处理R
inc(r);//inc(R)用完之后要注意减掉
if (odd(g)) and (odd(r)) then//这是根据当前g和r的数目做我上所述的相应操作
ans:=(ans+f[n-i,1,0]) mod 12345;
if (odd(g)) and (not odd(r)) then
ans:=(ans+f[n-i,1,1]) mod 12345;
if (not odd(g)) and (not odd(r)) then
ans:=(ans+f[n-i,0,1]) mod 12345;
if (not odd(g)) and (odd(r)) then
ans:=(ans+f[n-i,0,0]) mod 12345;
dec(r);
end;
end;
if not odd(g) or odd(r) then writeln('invalid') else//如果不满足要求输出无解信息,否则输出ans
writeln(ans);
end.

1.像g++,然后讨论完之后g--,这样的操作,前者是用来判断之后是加上奇或偶,而为什么要再减一呢?别忘了g是用来统计green的个数的,要用来判断输入样例是否合法,当然要使g的个数不变了;

2.感觉最重要的是要有排列组合的思想,推出边界条件很重要,推出状态转移方程很重要;

3.在计算f的时候要记得mod 12345

05-04 02:30