两排滚动数组

#include <iostream>

using namespace std;

int n,m;
int dp[2][30]={0};

int main()
{
    cin>>n>>m;
    int i,j,now,last;
    dp[0][0]=1;
    for(i=1;i<=m;i++)
    {
        now=i%2;
        last=(i+1)%2;
        for(j=0;j<n;j++)
        {
            dp[now][j]=dp[last][(j-1+n)%n]+dp[last][(j+1)%n];
        }
    }
    cout<<dp[now][0]<<endl;
    return 0;
}

a[i+1][j+1] a[i+1][j] a[i+1][j-1]
a[i][j+1] a[i][j] a[i][j-1] 关系图
a[i-1][j+1] a[i-1][j] a[i-1][j-1]

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <cstdlib>
#include <math.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop /
using namespace std;
int main(int argc, char* argv)
{
long long n,m,i,j,a[33][33];
cin>>n>>m;
memset(a,0,sizeof(a));

a[1][0]=1;
a[0][1]=1;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(j-1<1)
a[i][j]=a[i-1][n]+a[i-1][j+1];
else if(j+1>n)

a[i][j]=a[i-1][j-1]+a[i-1][1];
else
a[i][j]=a[i-1][j-1]+a[i-1][j+1];

}

}
cout<<a[m][1]<<endl;
return 0;
}

a[i+1][j+1] a[i+1][j] a[i+1][j-1]

a[i][j+1] a[i][j] a[i][j-1] 关系图

a[i-1][j+1] a[i-1][j] a[i-1][j-1]

附上代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <cstdlib>
#include <math.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop /
using namespace std;
int main(int argc, char* argv)
{
int n,m,i,j,a[33][33];
cin>>n>>m;
memset(a,0,sizeof(a));

a[1][0]=1;
a[0][1]=1;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(j-1<1) //表示最后一列
a[i][j]=a[i-1][n]+a[i-1][j+1];
else if(j+1>n) //表示第一列
a[i][j]=a[i-1][j-1]+a[i-1][1];
else
a[i][j]=a[i-1][j-1]+a[i-1][j+1];

}

}
cout<<a[m][1]<<endl;
return 0;
}
在 Pascal 语言中，sizeof() 是一种内存容量度量函数，功能是返回一个变量或者类型的大小（以字节为单位）；
memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值

Var
        n,m,i,j:longint;
        f:array[0..30,0..30]of longint;
Begin
        readln(n,m);
        f[1,0]:=1;
        for j:=1 to m do
                for i:=1 to n do
                begin
                        if i=1 then
                                f[i,j]:=f[n,j-1]+f[2,j-1];
                        if i=n then
                                f[i,j]:=f[1,j-1]+f[n-1,j-1];
                        if (i<>1) and (i<>n) then
                                f[i,j]:=f[i-1,j-1]+f[i+1,j-1];
                end;
        writeln(f[1,m]);
        readln;
End.

水是水，，但是我为啥还是写了那么久。。。tell me why。。。。

var
n,m,i,j:longint;
f:array[0..30,0..30] of longint;
begin
readln(n,m);
f[1,0]:=1;
for j:=1 to m do begin
f[1,j]:=f[2,j-1]+f[n,j-1];
for i:=2 to n-1 do begin
f[i,j]:=f[i-1,j-1]+f[i+1,j-1];
end;
f[n,j]:=f[n-1,j-1]+f[1,j-1];
end;
writeln(f[1,m]);
end.
简单递归

看来我想复杂了一点，搞出个三次方算法，不过照样秒杀。思路和p1603是一样的，只不过不必用矩阵乘法而已。

#include <stdio.h>

int matrix[50][50][50];

int main(){
int numV, times;
int i, j, l;

scanf("%d %d", &numV, &times);
for(l=0; l<=times; l++){
for(i=0; i<=numV; i++){
for(j=0; j<=numV; j++)
matrix[l][i][j] = 0;
}
}
for(i=1; i<=numV; i++)
matrix[0][i][i] = 1;

for(l=1; l<=times; l++){
for(i=1; i<=numV; i++){
for(j=1; j<=numV; j++){
matrix[l][i][j] += matrix[l-1][i][(j+numV-2)%numV+1]; //j-1 -> j
matrix[l][i][j] += matrix[l-1][i][j%numV+1]; //j+1 -> j
}
}
}

printf("%d\n", matrix[times][1][1]);

return 0;
}

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <cstdlib>
#include <math.h>
using namespace std;
int f[1001][1001];
int main(){
memset(f,0,sizeof(f));
int i,j,k,n,m;
cin>>n>>m;
f[0][1]=1;
f[1][0]=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(j-1<1) f[i][j]=f[i-1][n]+f[i-1][j+1];
else if(j+1>n) f[i][j]=f[i-1][j-1]+f[i-1][1];
else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}

cout<<f[m][1]<<endl;
system("pause");
return 0;
}

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <cstdlib>
#include <math.h>
using namespace std;
int f[1001][1001];
int main(){
memset(f,0,sizeof(f));
int i,j,k,n,m;
cin>>n>>m;
f[0][1]=1;
f[1][0]=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(j-1<1) f[i][j]=f[i-1][n]+f[i-1][j+1];
else if(j+1>n) f[i][j]=f[i-1][j-1]+f[i-1][1];
else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}

cout<<f[m][1]<<endl;
system("pause");
return 0;
}

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

main()
{
long n,m,i,j,f[31][31];
scanf("%ld %ld",&n,&m);
for (i=0;i<=n;i++)
for (j=0;j<=m;j++) f[i][j]=0;
f[0][1]=1;f[1][0]=1;
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)
if (i==1) f[i][j]=f[n][j-1]+f[i+1][j-1];
else if (i==n) f[i][j]=f[n-1][j-1]+f[1][j-1];
else f[i][j]=f[i-1][j-1]+f[i+1][j-1];
printf("%ld\n",f[1][m]);
}

类似过河卒。只不过把二维的棋盘这次弄成了一个圈。可以递推递归动态规划。递归我算了下。估计如果有不好的数据要到8 900MS，等会我测试下- -、显然这道题动态规划比较好写和简单、

第n次第m个人传到球的种数等于第n-1次第m个人左右2个人的种数之和
###pascal code
program P1485;
uses math;
var data:array[0..30,1..30] of longint;
i,j,n,m,num,s,a,b:longint;
begin
read(n,m); fillchar(data,sizeof(data),0);
data[0,1]:=1;
for i:=1 to m do
for j:=1 to n do
begin
s:=j; a:=s-1; b:=s+1; if a=0 then a:=n; if b=n+1 then b:=1;
data[i,j]:=data[i-1,a]+data[i-1,b];
end;
write(data[m,1]);
end.

DP瞬解

include <iostream>

include <algorithm>

using namespace std;
int a[33][33];
int main(){
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++){
a[i][min(i-1,31-i)]=1;
}
for(int j=1; j<=m; j++){
for(int i=1; i<=n; i++){
if(i==1) a[1][j]=a[n][j-1]+a[2][j-1];
if(i==n) a[i][j]=a[1][j-1]+a[i-1][j-1];
if(i>1&&i<n) a[i][j]=a[i-1][j-1]+a[i+1][j-1];
}
}
cout<<a[1][m]<<endl;
}

矩阵乘法

type arr=array[1..1000,1..1000] of longint;
var
a,w,b,g:arr;
m,n:longint;
procedure mul(var a,b,c:arr);
var
i,j,k:longint;
begin
fillchar(w,sizeof(w),0);
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
w[i][j]:=w[i][j]+a[i][k]*b[k][j];
for i:=1 to n do
for j:=1 to n do
c[i][j]:=w[i][j];
end;
procedure init;
var
i:longint;
begin
readln(n,m);
m:=m-1;
for i:=1 to n-1 do
begin
a[i][i+1]:=1;
a[i+1][i]:=1;
b[i][i+1]:=1;
b[i+1][i]:=1;
end;
a[1][n]:=1;a[n][1]:=1;
b[1][n]:=1;b[n][1]:=1;
end;
procedure solve;
begin
while(m<>0)do
begin
if(m and 1=1)then mul(a,b,a);
mul(b,b,b);
m:=m shr 1;
end;
end;
procedure print;
begin
writeln(a[1][1]);
end;
begin
init;
solve;
print;
end.

P1485传球游戏
Accepted

记录信息

评测状态 Accepted
题目 P1485 传球游戏
递交时间 2014-10-29 23:10:12
代码语言 C++
评测机 上海红茶馆
消耗时间 7 ms
消耗内存 564 KiB
评测时间 2014-10-29 23:10:13

评测结果

编译成功

foo.cpp: In function 'long long unsigned int dfs(int, int)':
foo.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 560 KiB, score = 10

测试数据 #6: Accepted, time = 7 ms, mem = 556 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 564 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10

Accepted, time = 7 ms, mem = 564 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

unsigned long long f[30 + 2][30 + 2];
int n , m;

unsigned long long dfs( int a , int b )
{
if( a == 1 && b == 0 )
return 1;
if( b == 0 )
return 0;
if( f[a][b] != -1 )
return f[a][b];
if( a != 1 && a != n )
{
f[a][b] = dfs( ( a + 1 ) % ( n + 1 ) , b - 1 ) + dfs( a - 1 , b - 1 );
return f[a][b];
}
else if( a == 1 )
{
f[a][b] = dfs( ( a + 1 ) % ( n + 1 ) , b - 1 ) + dfs( n , b - 1 );
return f[a][b];
}
f[a][b] = dfs( 1 , b - 1 ) + dfs( a - 1 , b - 1 );
return f[a][b];
}

int main()
{
while( scanf( "%d %d" , &n , &m ) != EOF )
{
memset( f , -1 , sizeof( f ) );
cout << dfs( 1 , m ) << endl;
}
return 0;
}

弱

Python

n, m = [int(x) for x in raw_input().split(' ')]
dp = [[0 if i > 0 else 1 for i in range(n)], []]
k = 0
for i in range(m):
dp[(k + 1) % 2] = [dp[k][(j + 1) % n] + dp[k][(j + n - 1) % n]
for j in range(n)]
k = (k + 1) % 2
print dp[k][0]

#include<stdio.h>
int main()
{
int n,m;
int a[40][40]={0};
a[3][1]=0,a[3][2]=2,a[3][3]=2,a[3][4]=6,a[3][5]=10,a[3][6]=22,a[3][7]=42,a[3][8]=86,a[3][9]=170,a[3][10]=342,a[3][11]=682,a[3][12]=1366,a[3][13]=2730,a[3][14]=5462,a[3][15]=10922,a[3][16]=21846,a[3][17]=43690,a[3][18]=87382,a[3][19]=174762,a[3][20]=349526,a[3][21]=699050,a[3][22]=1398102,a[3][23]=2796202,a[3][24]=5592406,a[3][25]=11184810,a[3][26]=22369622,a[3][27]=44739242,a[3][28]=89478486,a[3][29]=178956970,a[3][30]=357913942,a[4][1]=0,a[4][2]=2,a[4][3]=0,a[4][4]=8,a[4][5]=0,a[4][6]=32,a[4][7]=0,a[4][8]=128,a[4][9]=0,a[4][10]=512,a[4][11]=0,a[4][12]=2048,a[4][13]=0,a[4][14]=8192,a[4][15]=0,a[4][16]=32768,a[4][17]=0,a[4][18]=131072,a[4][19]=0,a[4][20]=524288,a[4][21]=0,a[4][22]=2097152,a[4][23]=0,a[4][24]=8388608,a[4][25]=0,a[4][26]=33554432,a[4][27]=0,a[4][28]=134217728,a[4][29]=0,a[4][30]=536870912,a[5][1]=0,a[5][2]=2,a[5][3]=0,a[5][4]=6,a[5][5]=2,a[5][6]=20,a[5][7]=14,a[5][8]=70,a[5][9]=72,a[5][10]=254,a[5][11]=330,a[5][12]=948,a[5][13]=1430,a[5][14]=3614,a[5][15]=6008,a[5][16]=13990,a[5][17]=24786,a[5][18]=54740,a[5][19]=101118,a[5][20]=215766,a[5][21]=409640,a[5][22]=854702,a[5][23]=1652090,a[5][24]=3396916,a[5][25]=6643782,a[5][26]=13530350,a[5][27]=26667864,a[5][28]=53971350,a[5][29]=106914242,a[5][30]=215492564,a[6][1]=0,a[6][2]=2,a[6][3]=0,a[6][4]=6,a[6][5]=0,a[6][6]=22,a[6][7]=0,a[6][8]=86,a[6][9]=0,a[6][10]=342,a[6][11]=0,a[6][12]=1366,a[6][13]=0,a[6][14]=5462,a[6][15]=0,a[6][16]=21846,a[6][17]=0,a[6][18]=87382,a[6][19]=0,a[6][20]=349526,a[6][21]=0,a[6][22]=1398102,a[6][23]=0,a[6][24]=5592406,a[6][25]=0,a[6][26]=22369622,a[6][27]=0,a[6][28]=89478486,a[6][29]=0,a[6][30]=357913942,a[7][1]=0,a[7][2]=2,a[7][3]=0,a[7][4]=6,a[7][5]=0,a[7][6]=20,a[7][7]=2,a[7][8]=70,a[7][9]=18,a[7][10]=252,a[7][11]=110,a[7][12]=924,a[7][13]=572,a[7][14]=3434,a[7][15]=2730,a[7][16]=12902,a[7][17]=12376,a[7][18]=48926,a[7][19]=54264,a[7][20]=187036,a[7][21]=232562,a[7][22]=720062,a[7][23]=980674,a[7][24]=2789164,a[7][25]=4086550,a[7][26]=10861060,a[7][27]=16878420,a[7][28]=42484682,a[7][29]=69242082,a[7][30]=166823430,a[8][1]=0,a[8][2]=2,a[8][3]=0,a[8][4]=6,a[8][5]=0,a[8][6]=20,a[8][7]=0,a[8][8]=72,a[8][9]=0,a[8][10]=272,a[8][11]=0,a[8][12]=1056,a[8][13]=0,a[8][14]=4160,a[8][15]=0,a[8][16]=16512,a[8][17]=0,a[8][18]=65792,a[8][19]=0,a[8][20]=262656,a[8][21]=0,a[8][22]=1049600,a[8][23]=0,a[8][24]=4196352,a[8][25]=0,a[8][26]=16781312,a[8][27]=0,a[8][28]=67117056,a[8][29]=0,a[8][30]=268451840,a[9][1]=0,a[9][2]=2,a[9][3]=0,a[9][4]=6,a[9][5]=0,a[9][6]=20,a[9][7]=0,a[9][8]=70,a[9][9]=2,a[9][10]=252,a[9][11]=22,a[9][12]=924,a[9][13]=156,a[9][14]=3432,a[9][15]=910,a[9][16]=12870,a[9][17]=4760,a[9][18]=48622,a[9][19]=23256,a[9][20]=184796,a[9][21]=108528,a[9][22]=705894,a[9][23]=490314,a[9][24]=2708204,a[9][25]=2163150,a[9][26]=10430500,a[9][27]=9373652,a[9][28]=40313160,a[9][29]=40060078,a[9][30]=156305070,a[10][1]=0,a[10][2]=2,a[10][3]=0,a[10][4]=6,a[10][5]=0,a[10][6]=20,a[10][7]=0,a[10][8]=70,a[10][9]=0,a[10][10]=254,a[10][11]=0,a[10][12]=948,a[10][13]=0,a[10][14]=3614,a[10][15]=0,a[10][16]=13990,a[10][17]=0,a[10][18]=54740,a[10][19]=0,a[10][20]=215766,a[10][21]=0,a[10][22]=854702,a[10][23]=0,a[10][24]=3396916,a[10][25]=0,a[10][26]=13530350,a[10][27]=0,a[10][28]=53971350,a[10][29]=0,a[10][30]=215492564,a[11][1]=0,a[11][2]=2,a[11][3]=0,a[11][4]=6,a[11][5]=0,a[11][6]=20,a[11][7]=0,a[11][8]=70,a[11][9]=0,a[11][10]=252,a[11][11]=2,a[11][12]=924,a[11][13]=26,a[11][14]=3432,a[11][15]=210,a[11][16]=12870,a[11][17]=1360,a[11][18]=48620,a[11][19]=7752,a[11][20]=184756,a[11][21]=40698,a[11][22]=705434,a[11][23]=201894,a[11][24]=2704204,a[11][25]=961400,a[11][26]=10401250,a[11][27]=4440150,a[11][28]=40123152,a[11][29]=20030010,a[11][30]=155172330,a[12][1]=0,a[12][2]=2,a[12][3]=0,a[12][4]=6,a[12][5]=0,a[12][6]=20,a[12][7]=0,a[12][8]=70,a[12][9]=0,a[12][10]=252,a[12][11]=0,a[12][12]=926,a[12][13]=0,a[12][14]=3460,a[12][15]=0,a[12][16]=13110,a[12][17]=0,a[12][18]=50252,a[12][19]=0,a[12][20]=194446,a[12][21]=0,a[12][22]=758100,a[12][23]=0,a[12][24]=2973350,a[12][25]=0,a[12][26]=11716252,a[12][27]=0,a[12][28]=46333566,a[12][29]=0,a[12][30]=183739940,a[13][1]=0,a[13][2]=2,a[13][3]=0,a[13][4]=6,a[13][5]=0,a[13][6]=20,a[13][7]=0,a[13][8]=70,a[13][9]=0,a[13][10]=252,a[13][11]=0,a[13][12]=924,a[13][13]=2,a[13][14]=3432,a[13][15]=30,a[13][16]=12870,a[13][17]=272,a[13][18]=48620,a[13][19]=1938,a[13][20]=184756,a[13][21]=11970,a[13][22]=705432,a[13][23]=67298,a[13][24]=2704156,a[13][25]=354200,a[13][26]=10400602,a[13][27]=1776060,a[13][28]=40116656,a[13][29]=8584290,a[13][30]=155118390,a[14][1]=0,a[14][2]=2,a[14][3]=0,a[14][4]=6,a[14][5]=0,a[14][6]=20,a[14][7]=0,a[14][8]=70,a[14][9]=0,a[14][10]=252,a[14][11]=0,a[14][12]=924,a[14][13]=0,a[14][14]=3434,a[14][15]=0,a[14][16]=12902,a[14][17]=0,a[14][18]=48926,a[14][19]=0,a[14][20]=187036,a[14][21]=0,a[14][22]=720062,a[14][23]=0,a[14][24]=2789164,a[14][25]=0,a[14][26]=10861060,a[14][27]=0,a[14][28]=42484682,a[14][29]=0,a[14][30]=166823430,a[15][1]=0,a[15][2]=2,a[15][3]=0,a[15][4]=6,a[15][5]=0,a[15][6]=20,a[15][7]=0,a[15][8]=70,a[15][9]=0,a[15][10]=252,a[15][11]=0,a[15][12]=924,a[15][13]=0,a[15][14]=3432,a[15][15]=2,a[15][16]=12870,a[15][17]=34,a[15][18]=48620,a[15][19]=342,a[15][20]=184756,a[15][21]=2660,a[15][22]=705432,a[15][23]=17710,a[15][24]=2704156,a[15][25]=106260,a[15][26]=10400600,a[15][27]=592020,a[15][28]=40116600,a[15][29]=3121560,a[15][30]=155117522,a[16][1]=0,a[16][2]=2,a[16][3]=0,a[16][4]=6,a[16][5]=0,a[16][6]=20,a[16][7]=0,a[16][8]=70,a[16][9]=0,a[16][10]=252,a[16][11]=0,a[16][12]=924,a[16][13]=0,a[16][14]=3432,a[16][15]=0,a[16][16]=12872,a[16][17]=0,a[16][18]=48656,a[16][19]=0,a[16][20]=185136,a[16][21]=0,a[16][22]=708512,a[16][23]=0,a[16][24]=2725408,a[16][25]=0,a[16][26]=10532160,a[16][27]=0,a[16][28]=40870080,a[16][29]=0,a[16][30]=159189120,a[17][1]=0,a[17][2]=2,a[17][3]=0,a[17][4]=6,a[17][5]=0,a[17][6]=20,a[17][7]=0,a[17][8]=70,a[17][9]=0,a[17][10]=252,a[17][11]=0,a[17][12]=924,a[17][13]=0,a[17][14]=3432,a[17][15]=0,a[17][16]=12870,a[17][17]=2,a[17][18]=48620,a[17][19]=38,a[17][20]=184756,a[17][21]=420,a[17][22]=705432,a[17][23]=3542,a[17][24]=2704156,a[17][25]=25300,a[17][26]=10400600,a[17][27]=161460,a[17][28]=40116600,a[17][29]=950040,a[17][30]=155117520,a[18][1]=0,a[18][2]=2,a[18][3]=0,a[18][4]=6,a[18][5]=0,a[18][6]=20,a[18][7]=0,a[18][8]=70,a[18][9]=0,a[18][10]=252,a[18][11]=0,a[18][12]=924,a[18][13]=0,a[18][14]=3432,a[18][15]=0,a[18][16]=12870,a[18][17]=0,a[18][18]=48622,a[18][19]=0,a[18][20]=184796,a[18][21]=0,a[18][22]=705894,a[18][23]=0,a[18][24]=2708204,a[18][25]=0,a[18][26]=10430500,a[18][27]=0,a[18][28]=40313160,a[18][29]=0,a[18][30]=156305070,a[19][1]=0,a[19][2]=2,a[19][3]=0,a[19][4]=6,a[19][5]=0,a[19][6]=20,a[19][7]=0,a[19][8]=70,a[19][9]=0,a[19][10]=252,a[19][11]=0,a[19][12]=924,a[19][13]=0,a[19][14]=3432,a[19][15]=0,a[19][16]=12870,a[19][17]=0,a[19][18]=48620,a[19][19]=2,a[19][20]=184756,a[19][21]=42,a[19][22]=705432,a[19][23]=506,a[19][24]=2704156,a[19][25]=4600,a[19][26]=10400600,a[19][27]=35100,a[19][28]=40116600,a[19][29]=237510,a[19][30]=155117520,a[20][1]=0,a[20][2]=2,a[20][3]=0,a[20][4]=6,a[20][5]=0,a[20][6]=20,a[20][7]=0,a[20][8]=70,a[20][9]=0,a[20][10]=252,a[20][11]=0,a[20][12]=924,a[20][13]=0,a[20][14]=3432,a[20][15]=0,a[20][16]=12870,a[20][17]=0,a[20][18]=48620,a[20][19]=0,a[20][20]=184758,a[20][21]=0,a[20][22]=705476,a[20][23]=0,a[20][24]=2704708,a[20][25]=0,a[20][26]=10405800,a[20][27]=0,a[20][28]=40157550,a[20][29]=0,a[20][30]=155402532,a[21][1]=0,a[21][2]=2,a[21][3]=0,a[21][4]=6,a[21][5]=0,a[21][6]=20,a[21][7]=0,a[21][8]=70,a[21][9]=0,a[21][10]=252,a[21][11]=0,a[21][12]=924,a[21][13]=0,a[21][14]=3432,a[21][15]=0,a[21][16]=12870,a[21][17]=0,a[21][18]=48620,a[21][19]=0,a[21][20]=184756,a[21][21]=2,a[21][22]=705432,a[21][23]=46,a[21][24]=2704156,a[21][25]=600,a[21][26]=10400600,a[21][27]=5850,a[21][28]=40116600,a[21][29]=47502,a[21][30]=155117520,a[22][1]=0,a[22][2]=2,a[22][3]=0,a[22][4]=6,a[22][5]=0,a[22][6]=20,a[22][7]=0,a[22][8]=70,a[22][9]=0,a[22][10]=252,a[22][11]=0,a[22][12]=924,a[22][13]=0,a[22][14]=3432,a[22][15]=0,a[22][16]=12870,a[22][17]=0,a[22][18]=48620,a[22][19]=0,a[22][20]=184756,a[22][21]=0,a[22][22]=705434,a[22][23]=0,a[22][24]=2704204,a[22][25]=0,a[22][26]=10401250,a[22][27]=0,a[22][28]=40123152,a[22][29]=0,a[22][30]=155172330,a[23][1]=0,a[23][2]=2,a[23][3]=0,a[23][4]=6,a[23][5]=0,a[23][6]=20,a[23][7]=0,a[23][8]=70,a[23][9]=0,a[23][10]=252,a[23][11]=0,a[23][12]=924,a[23][13]=0,a[23][14]=3432,a[23][15]=0,a[23][16]=12870,a[23][17]=0,a[23][18]=48620,a[23][19]=0,a[23][20]=184756,a[23][21]=0,a[23][22]=705432,a[23][23]=2,a[23][24]=2704156,a[23][25]=50,a[23][26]=10400600,a[23][27]=702,a[23][28]=40116600,a[23][29]=7308,a[23][30]=155117520,a[24][1]=0,a[24][2]=2,a[24][3]=0,a[24][4]=6,a[24][5]=0,a[24][6]=20,a[24][7]=0,a[24][8]=70,a[24][9]=0,a[24][10]=252,a[24][11]=0,a[24][12]=924,a[24][13]=0,a[24][14]=3432,a[24][15]=0,a[24][16]=12870,a[24][17]=0,a[24][18]=48620,a[24][19]=0,a[24][20]=184756,a[24][21]=0,a[24][22]=705432,a[24][23]=0,a[24][24]=2704158,a[24][25]=0,a[24][26]=10400652,a[24][27]=0,a[24][28]=40117356,a[24][29]=0,a[24][30]=155125640,a[25][1]=0,a[25][2]=2,a[25][3]=0,a[25][4]=6,a[25][5]=0,a[25][6]=20,a[25][7]=0,a[25][8]=70,a[25][9]=0,a[25][10]=252,a[25][11]=0,a[25][12]=924,a[25][13]=0,a[25][14]=3432,a[25][15]=0,a[25][16]=12870,a[25][17]=0,a[25][18]=48620,a[25][19]=0,a[25][20]=184756,a[25][21]=0,a[25][22]=705432,a[25][23]=0,a[25][24]=2704156,a[25][25]=2,a[25][26]=10400600,a[25][27]=54,a[25][28]=40116600,a[25][29]=812,a[25][30]=155117520,a[26][1]=0,a[26][2]=2,a[26][3]=0,a[26][4]=6,a[26][5]=0,a[26][6]=20,a[26][7]=0,a[26][8]=70,a[26][9]=0,a[26][10]=252,a[26][11]=0,a[26][12]=924,a[26][13]=0,a[26][14]=3432,a[26][15]=0,a[26][16]=12870,a[26][17]=0,a[26][18]=48620,a[26][19]=0,a[26][20]=184756,a[26][21]=0,a[26][22]=705432,a[26][23]=0,a[26][24]=2704156,a[26][25]=0,a[26][26]=10400602,a[26][27]=0,a[26][28]=40116656,a[26][29]=0,a[26][30]=155118390,a[27][1]=0,a[27][2]=2,a[27][3]=0,a[27][4]=6,a[27][5]=0,a[27][6]=20,a[27][7]=0,a[27][8]=70,a[27][9]=0,a[27][10]=252,a[27][11]=0,a[27][12]=924,a[27][13]=0,a[27][14]=3432,a[27][15]=0,a[27][16]=12870,a[27][17]=0,a[27][18]=48620,a[27][19]=0,a[27][20]=184756,a[27][21]=0,a[27][22]=705432,a[27][23]=0,a[27][24]=2704156,a[27][25]=0,a[27][26]=10400600,a[27][27]=2,a[27][28]=40116600,a[27][29]=58,a[27][30]=155117520,a[28][1]=0,a[28][2]=2,a[28][3]=0,a[28][4]=6,a[28][5]=0,a[28][6]=20,a[28][7]=0,a[28][8]=70,a[28][9]=0,a[28][10]=252,a[28][11]=0,a[28][12]=924,a[28][13]=0,a[28][14]=3432,a[28][15]=0,a[28][16]=12870,a[28][17]=0,a[28][18]=48620,a[28][19]=0,a[28][20]=184756,a[28][21]=0,a[28][22]=705432,a[28][23]=0,a[28][24]=2704156,a[28][25]=0,a[28][26]=10400600,a[28][27]=0,a[28][28]=40116602,a[28][29]=0,a[28][30]=155117580,a[29][1]=0,a[29][2]=2,a[29][3]=0,a[29][4]=6,a[29][5]=0,a[29][6]=20,a[29][7]=0,a[29][8]=70,a[29][9]=0,a[29][10]=252,a[29][11]=0,a[29][12]=924,a[29][13]=0,a[29][14]=3432,a[29][15]=0,a[29][16]=12870,a[29][17]=0,a[29][18]=48620,a[29][19]=0,a[29][20]=184756,a[29][21]=0,a[29][22]=705432,a[29][23]=0,a[29][24]=2704156,a[29][25]=0,a[29][26]=10400600,a[29][27]=0,a[29][28]=40116600,a[29][29]=2,a[29][30]=155117520,a[30][1]=0,a[30][2]=2,a[30][3]=0,a[30][4]=6,a[30][5]=0,a[30][6]=20,a[30][7]=0,a[30][8]=70,a[30][9]=0,a[30][10]=252,a[30][11]=0,a[30][12]=924,a[30][13]=0,a[30][14]=3432,a[30][15]=0,a[30][16]=12870,a[30][17]=0,a[30][18]=48620,a[30][19]=0,a[30][20]=184756,a[30][21]=0,a[30][22]=705432,a[30][23]=0,a[30][24]=2704156,a[30][25]=0,a[30][26]=10400600,a[30][27]=0,a[30][28]=40116600,a[30][29]=0,a[30][30]=155117522;
scanf("%d %d",&n,&m);
printf("%d",a[n][m]);
return 0;
}

var k,i,j,n,m:longint;
f:array[1..40,0..40]of longint;
begin
readln(n,m);
f[1,0]:=1;
for i:=0 to m-1 do
for j:=1 to n do
if f[j,i]<>0 then begin
if j=1 then begin
inc(f[j+1,i+1],f[j,i]);
inc(f[n,i+1],f[j,i]);
continue;
end;
if j=n then begin
inc(f[j-1,i+1],f[j,i]);
inc(f[1,i+1],f[j,i]);
continue;
end;
inc(f[j+1,i+1],f[j,i]);
inc(f[j-1,i+1],f[j,i]);
end;
writeln(f[1,m]);
end.
DP的关键是顺序，能推上来的，这样一定是正确的。切勿将N的循环放在外边。

#include <stdio.h>
int tep[100][100];
int main()
{
int i,j,n,time;
scanf("%d%d",&n,&time);
for(i=0;i<100;i++)
for(j=0;j<100;j++)
tep[i][j]=0;
tep[0][1]=1;tep[0][n+1]=1;
for(i=1;i<=time;i++)
{
for(j=1;j<=n;j++)
{
tep[i][j]=tep[i-1][j-1]+tep[i-1][j+1];

}
tep[i][1]+=tep[i][n+1],tep[i][n+1]=tep[i][1];
tep[i][n]+=tep[i][0],tep[i][0]=tep[i][n];
}
printf("%d",tep[time][1]);
}

水体 1，n的边界 动规 ok。。

var f:array[-1..40,-1..40] of longint;

    n,m,k,i:integer;

begin

  readln(n,m);

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

  f[0,1]:=1;

  f[2,1]:=1;

  f[n,1]:=1;

  for k:=2 to m-1 do

    for i:=1 to n do

      if i=1 then f:=f[n,k-1]+f

        else if i=n then f:=f+f[1,k-1]

         else f:=f+f;

  writeln(f[n,m-1]+f[2,m-1]);

end.

轻微猥琐的一道题。。。。。。。。

点这里查看程序源码+详细题解

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted/ 100 / 0ms / 620KB

用递归超时……

没办法，写了个矩阵