#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
ll f[1001][101],ans,n,t;
int main()
{
    scanf("%d%d",&t,&n);
    For(i,0,t-1)    f[1][i]=1;
    For(i,1,n)
    {
        For(j,0,t-1)
            For(k,0,t-1)
                if(abs(j-k)!=1)
                    f[i][j]+=f[i-1][k];
    }
    For(i,1,t-1)
        ans+=f[n][i];
    printf("%lld\n",ans);
}
...神他妈没数据范围

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int k,l;
long long a[1002][102],ans=0;

int main()
{
    scanf("%d%d",&k,&l);
    a[0][0]=0;
    for (int s=1;s<k;s++) a[0][s]=1;
    for (int s=1;s<l;s++)
        for (int t=0;t<k;t++)
            for (int r=0;r<k;r++)
                if (r!=t-1&&r!=t+1)
                    a[s][r]+=a[s-1][t];
    for (int s=0;s<k;s++) ans+=a[l-1][s];
    printf("%lld",ans);
}

没想dp却用另一种方式推出了dp的样子

辣鸡题，不给数据范围，答案要用long long。不然溢出一个点。

#include<cstdio>
#include<cstring>
using namespace std;

long long int info[100][1000],ans=0;
int k,l;

void dfs(int last,int now)
{
    long long int temp=ans;
    for(int i=0;i<k;i++)
        if(last!=i-1&&last!=i+1)
        {
            if(now==l) ans+=1;
            else if(info[i][now+1]!=-1) ans+=info[i][now+1];
            else dfs(i,now+ 1);
        }
    if(last!=-1) info[last][now]=ans-temp;
}

int main()
{
    scanf("%d%d",&k,&l);
    memset(info,-1,sizeof(info));
    
    dfs(-1,1);
    printf("%lld\n",ans);
    return 0;
}

var n,m,i,j,k:integer;
a:array[1..1000,0..1000]of qword;
tot:qword;
begin
read(m,n);
m:=m-1;
for j:=0 to m do a[1,j]:=1;
for i:=2 to n do
for j:=0 to m do
for k:=0 to m do
if abs(k-j)<>1 then
inc(a,a);
tot:=0;
for j:=1 to m do inc(tot,a[n,j]);
write(tot);
end.
坑爹啊！又没写递归式！！！！！
自己琢磨个半天~~~~~

目测数据范围是n,k<=20......
不需要高精.

记得qword。。。。。orz

编译通过...

├ 测试数据 01：答案正确... (0ms, 584KB)

├ 测试数据 02：答案正确... (0ms, 584KB)

├ 测试数据 03：答案正确... (0ms, 584KB)

├ 测试数据 04：答案正确... (0ms, 584KB)

├ 测试数据 05：答案正确... (0ms, 584KB)

├ 测试数据 06：答案正确... (0ms, 584KB)

├ 测试数据 07：答案正确... (0ms, 584KB)

├ 测试数据 08：答案正确... (0ms, 584KB)

├ 测试数据 09：答案正确... (0ms, 584KB)

├ 测试数据 10：答案正确... (0ms, 584KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 584KB

无聊的写了个一个一个判断，不出所料，超时6个点……

还是要用动规啊

当练练DP吧。。

首位不为0！！！

qword可过

写一个搜索可得70分。（数据还是很弱）

DP+EXTENDED 可得100分。

Accepted 有效得分：100 有效耗时：0ms

BS这水题！！

考虑到l=1用了特派，结果错了。然后拿掉特派，居然过了！！

试问1位时0难道就不可以吗？

ORZ...DP.....

没想出DP的沙茶飘过.....

这就是动态规划啊！

for i:=1 to n do

for j:=0 to m do

for k:=0 to m do

if k-j1 and k-j-1 then

f:=f+f;

o(n^3) 0ms

f 长度为i,开头为j的k好数个数

f=sigma(f) {(0

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

动态规划可以秒杀！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

total:double;

j,g,k,l,i:integer;

f:array[0..20,0..20]of int64;

begin

read(k,l);

for i:=0 to k-1 do

f[1,i]:=1;

for i:=2 to l do

for j:=0 to k-1 do

for g:=0 to k-1 do

if (g(j+1))and(g(j-1))then f:=f+f;

for i:=1 to k-1 do

total:=total+f[l,i];

writeln(total:0:0);

end.

范围比较大

同志们

你们认为存在一个数 首位是0的吗？

比如说：012

这是数字吗

S=(n-1)*(n-2)^(m-1)+1对吗

很轻松~~~~

0开头的都不算哦~~~ 不过话说现在自然数好象是包括0的，不懂~~~~

记得要用qword啊！or 高精度才过，交了n次