我用到了兩個(gè)數(shù)組，d1[n]表示長(zhǎng)度為n的牛肉串最后一個(gè)字符不是'O'，d2[n]表示長(zhǎng)度為n的牛肉串最后一個(gè)字符是'O'。這樣結(jié)果就是d1[n]+d2[n]；
對(duì)于已經(jīng)得到了長(zhǎng)度為n-1的牛肉串，我們可以來討論在第n個(gè)位置放置何種字符的牛肉串。
已得到第n-1個(gè)位置的字符第n個(gè)位置需要放置的字符結(jié)果
不是'O'不是'O'得到長(zhǎng)度為n的，結(jié)尾不是'O'的字符串
不是'O'是'O'得到長(zhǎng)度為n的，結(jié)尾是'O'的字符串
是'O'不是'O'得到長(zhǎng)度為n的，結(jié)尾不是'O'的字符串
是'O'是'O'不成立
所以，動(dòng)態(tài)規(guī)劃方程就很容易得出來了。
#include<stdio.h>
__int64 d0[40],d1[40];//以0與非0結(jié)尾39害我調(diào)試了N久
int main()
{
d0[0]=1;
d1[0]=2;
printf("%I64d %I64d \n",d0[0],d1[0]);
for(int i=1;i<40;i++)
{
d0[i]=d1[i-1];//前一個(gè)非0的就是這一個(gè)要以0結(jié)尾的
d1[i]=2*d1[i-1]+d0[i-1]*2;//前一個(gè)非0的與以0的都要乘以2
}
int n;
while((scanf("%d",&n))!=EOF)
{
printf("%I64d %I64d \n",d0[0],d1[0]);
printf("%I64d %I64d \n",d0[n-1],d1[n-1]);
printf("%I64d\n",d0[n-1]+d1[n-1]);
}
return 0;
}
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
