题意:给你一个无限大的棋盘,一个象棋中的马,问你这个马,飞n步后,可能的位置有多少种?
题解:看到题,就想先打表试试,于是先写个暴力(枚举每个位置,是马就飞周围8个格子,注意不要在同个循环里把格子的标记涂成相同的数字)
然后打出来是9 41 109 205 325 473 649 853
对于这种增长不快的,我一般是先直接两项相减
得到 32 68 96 120 148 176 204
这时就看到,这个数列的增长越来越有趣? 后面都加的是28?
于是对于n>=5,我们有 f[n]=f[n-1]+120+(n-5)*28 = f[n-1]+28*n-20
这种递推式很明显的 解法 f[n] = f[n-1]+28*n-20
f[n-1]= f[n-2]+28*(n-1)-20
f[5]=f[4]+28*(5)-20
左右相加,再抵消.
f[n]=28*(n+n-1+...+5)-20*(n-5+1)=f[4]+28*(n+5)*(n-4)/2-20*(n-4)=(14*(n+5)-20)*(n-4)+205 = (14*n+50)*(n-4)+205
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 int main() 5 { 6 int caseCnt; 7 scanf("%d",&caseCnt); 8 for(int t=1;t<=caseCnt;++t) { 9 ll n; 10 scanf("%llu",&n); 11 ll ans; 12 if(n==0) ans=1; 13 else if(n==1) ans=9; 14 else if(n==2) ans=41; 15 else if(n==3) ans=109; 16 else if(n==4) ans=205; 17 else { 18 ans=(14*n+50)*(n-4)+205; 19 } 20 printf("Case #%d: %llu ",t,ans); 21 } 22 return 0; 23 }