题目链接：http://poj.org/problem?id=1953
一列数，每位只能是0和1，问使1不连续的序列有多少种？
最先开始的思路是递归，可是递归的败病就在这里，递归层数过多，处理长数据会超时，但是思路应该是没问题了！来看看代码把！
代码如下：
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;
int ct,n,d[50];
void dp(int k,int i)
{
if(k==n-1)
{
ct++;
return;
}
d[k]=i;
if(d[k]==0)
dp(k+1,1);
dp(k+1,0);
}
int main()
{
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
ct=0;
cin>>n;
dp(0,0);
dp(0,1);
cout<<"Scenario #"<<i<<":"<<endl<<ct<<endl<<endl;
}
}
|
代码如下：
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int t,ct,n,d[50][2];
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n;
d[1][1]=1;
d[1][0]=1;
for(int j=2;j<=n;j++)
{
d[j][1]=d[j-1][0];
d[j][0]=d[j-1][1]+d[j-1][0];
}
ct=d[n][1]+d[n][0];
cout<<"Scenario #"<<i<<":"<<endl<<ct<<endl<<endl;
}
}
|