没有想到dp，写了个矩阵乘法。。。。。

var

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

i,j,l,n,m,k:longint;

begin

readln(n,m);

f[0,1]:=1;

for i:=1 to m do

for j:=2 to n-1 do

begin

f:=f+f;

f:=f+f;

f:=f+f;

end;

write(f[m,1]);

end.

Program P1485;

Var n,m:integer;

ans:longint;

Procedure cross(a,b:integer);

var c:integer;

begin

if b=0 then

begin

if a=0 then inc(ans);

exit

end;

cross((a+1)mod n,b-1);

cross((a-1)mod n,b-1)

end;

Begin

read(n,m);

ans:=0;

cross(0,m);

write(ans)

End.

递归超时了，无语

排列组合

普及组的都几乎搞不定，我真天才！

#include

#include

#define maxn 40

int main()

{

int i, j, n, m, s[maxn][maxn];

scanf("%d%d", &n, &m);

memset(s, 0, sizeof(s));

s[0][0] = 1;

for(i=1; i

没想到……在我的邮箱里竟然有这个题目的点评，也不记得是什么时候写的了 顺带发上来留个名字吧……

引“这个题目不错，一开始，我是用搜索的方法来解决的，小数据挺管用，大数据就不行了，后来又想到，上次和学长的做的“出栈序列”的题目，于是决定用数组优化，并把‘过程’改为‘函数’，递归函数中数组a[x，y]记录每种情况的答案，收到了不错的效果。

另外，有种特殊情况（n为偶数，m为奇数时），答案肯定为0，我也把它写了进去，时间也有一定的优化。

其实，我没有完全理解题目意思，比如，当n=3，m=2 时，1-->2-->1（或1-->3-->1）是否也是一种答案呢，我把它当作“是”的情况来考虑。”

PS：记忆化搜索……

var n,m,i,j,a,b:longint;

f:array[1..100,1..100] of int64;

begin

readln(n,m);

f[2,1]:=1; f[n,1]:=1;

for j:=2 to m do

for i:=1 to n do

begin

a:=i+1; b:=i-1;

if a=n+1 then a:=1;

if b=0 then b:=n;

f:=f[a,j-1]+f;

end;

writeln(f[1,m]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

妈的，水体也交3次才AC！汗

编译通过...

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

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

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

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

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

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

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

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

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

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

program p1485;

var

m,n,i,j:integer;

f:array[0..100,0..100]of longint;

begin

readln(m,n);

f[1,2]:=1;

f[1,m]:=1;

for i:=1 to n do begin

for j:=2 to m do

if j=m then f:=f+f+f

else f:=f+f+f;

f:=f+f+f;

end;

writeln(f[n,1]);

end.

f表示传到第i次球，球在j这个人手上时的个数

轻松得到f的转移方程：

f:=f+f

特殊处理一下j=1或n时的方程即可。

边界：f[1,2]:=1 f[1,n]:=1

编译通过...

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

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

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

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

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

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

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

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

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

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

var

n,m:integer;

f:array[0..30,0..30]of longint;

procedure init;

begin

readln(n,m);

fillchar(f,sizeof(f),0);

f[0,1]:=1;

end;

procedure work;

var

i,j:integer;

begin

for i:=1 to m do

for j:=1 to n do

begin

if j=1 then f:=f+f

else if j=n then f:=f+f

else f:=f+f;

end;

end;

procedure print;

begin

writeln(f[m,1]);

end;

begin

init;

work;

print;

end.

简单DP

f[k,i]表示传k次后到第i个人的方案数

f[k,i]=f[k-1,i-1]+f[k-1,i+1]

边界f[0,1]=1就可以

i=n 时 和 i=1 时要单独处理下

---|---|---|---|---|---|---|---|---|--晒程序---|---|---|---|---|---|---|---|---|---|-

program p1485;

var

f:array[0..30,0..30]of longint;

n,m,i,j:longint;

begin

readln(n,m);

f[0,1]:=1;

for i:=1 to m do

for j:=1 to n do

if j=1 then f:=f+f

else

if j=n then f:=f+f

else f:=f+f;

writeln(f[m,1]);

end.

f表示第m次传到第i个人的方案数

f=f+f

边界条件

从左边传或者从右边过传了k个人也传了k次的时候,显然为1

f显然为0

DP的时候只要注意一下环状结构.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ball(input,output);

var n,m,i,xx:longint;

ab:array [0..30,0..30] of longint;

begin

readln(n,m);

ab[1,0]:=1;

for i:=2 to n do

ab:=0;

for i:=1 to m do

for xx:=1 to n do

if xx=1

then ab[1,i]:=ab[n,i-1]+ab[2,i-1]

else if xx=n

then ab[n,i]:=ab[n-1,i-1]+ab[1,i-1]

else ab[xx,i]:=ab[xx-1,i-1]+ab[xx+1,i-1];

writeln(ab[1,m]);

end.

搜索……递推……动规……

三种不同的得分！！！！！

program p1485;

const

maxn=5;maxm=5;

var

f:array[0..maxm,1..maxn]of longint;

n,m,i,j:longint;

begin

readln(n,m);

fillchar(f,sizeof(f),0);

f[0,1]:=1;

for i:=1 to m do

for j:=1 to n do

if (j1) and (jn) then f:=f+f

else if (j=1) then f:=f+f

else f:=f+f;

writeln(f[m,1]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var f:array[0..100,0..100] of longint;

x,y,i,j,n,m:longint;

begin

fillchar(f,sizeof(f),0);

readln(n,m);

f[1,0]:=1;

if (m=1) and (n1) then begin writeln('0'); halt; end;

for j:=1 to m do

for i:=1 to n do

begin

x:=i-1; if x=0 then x:=n;

y:=i+1; if y=n+1 then y:=1;

f:=f[x,j-1]+f[y,j-1];

end;

writeln(f[1,m]);

end.

我dp方程知道，但交了N次还是不成，借鉴了一下题解，见谅……

事实证明：

没有剪枝的暴搜是不行的......

DP万岁！！！

膜拜。这样交表= =

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索+两个超强剪枝=AC

单纯记忆化第七个要超时

膜拜一下打表的神牛

去年这题栽了，现在才发现，简单得无语……

var

n,i,j,m,l,r:longint;

f,x:array[1..30] of longint;

begin

read(n,m);

x[1]:=1;f[1]:=1;

for i:=1 to m do

begin

for j:=1 to n do

begin

l:=j-1;

r:=j+1;

if l=0 then l:=n;

if r=n+1 then r:=1;

f[j]:=x[l]+x[r];

end;

for j:=1 to n do

x[j]:=f[j];

end;

writeln(f[1]);

end.