3051. 台阶走法数

这不是水题吗……

居然比台阶坏了的那题还值钱。。

include

using namespace std;
int main()
{
int T;
cin>>T;
for(int t = 0; t < T; t++)
{
int item;
cin>>item;
long long step[51];
step[1] = 1, step[2] = 2, step[3] = 4, step[4] = 8;
for(int t = 5; t < 51; t++) step[t] = step[t-1]+step[t-2]+step[t-3]+step[t-4];
cout<<”case #”<<t<<’:’<<endl;
cout<<step[item]<<endl;
}
}

1+2和2+1是两种不同走法

include

using namespace std;
int T;
long long dp[51];
void init()
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=50;i++)
for(int j=1;j<=4;j++)
if(i-j>=0) dp[i]+=dp[i-j];
return;
}
void solve()
{
int n;
cin>>n;
cout<<dp[n]<<endl;
return;
}

int main()
{
scanf(“%d”,&T);
init();
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

import java.util.;
//import java.text.;
//import java.io.;
//import java.time.;
//import java.time.format.*;

public class Main
{
public static void main(String[] args)
{
long[] a = new long[51];
a[1] = 1; a[2] = 2; a[3] = 4; a[4] = 8;
for(int i = 5; i < 51; ++i)
a[i] = a[i-1] + a[i-2] + a[i-3] + a[i-4];
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for(int i = 0; i < num; ++i)
{
int index = sc.nextInt();
System.out.println(“case #”+i+”:\n”+a[index]);
}
sc.close();
}
}

模板用I64d输出？

T = int(input())
for i in range(T):
n = int(input())
if n == 1:
print(“case #%d:\n%d” % (i, 1))
elif n == 2:
print(“case #%d:\n%d” % (i, 2))
elif n == 3:
print(“case #%d:\n%d” % (i, 4))
elif n == 4:
print(“case #%d:\n%d” % (i, 8))
elif n > 4:
L = [k for k in range(n)]
L[0] = 1
L[1] = 2
L[2] = 4
L[3] = 8
for j in range(4,n):
L[j] = L[j - 1] + L[j - 2] + L[j - 3] + L[j - 4]
print(“case #%d:\n%d” % (i,L[n-1]))

ll a[maxn];

void init(){
memset(a, 0, sizeof(a));
a[1]=1;
a[2]=2;
a[3]=4;
a[4]=8;
for(int i=5;i<=50;i++)
a[i]=a[i-1]+a[i-2]+a[i-3]+a[i-4];
}

int main(int argc, const char * argv[]) {
init();
int cas;
cin>>cas;
for(int i=0;i<cas;i++){
int n;
scanf(“%d”,&n);
printf(“case #%d:\n”,i);
printf(“%lld\n”,a[n]);
}
return 0;
}

动态规划基础题居然有5.2EMB？！