本文共 784 字，大约阅读时间需要 2 分钟。
状态：dp[k,i]：k分钟后，毛毛虫爬到第i个位置的方案数
状态转移方程： dp[k,i]= { dp[k-1,i-1] i=n; dp[k-1,i+1] i=1; dp[k-1,i-1]+dp[k-1,i+1] } 边界处理： i=P+k||P=i+k,dp[k,i]=1; else dp[k,i]=0;代码如下；
#include#include #include using namespace std;int dp[102][102];int main(){ int N,P,M,T; int i,j,k,flag; while(~scanf("%d%d%d%d",&N,&P,&M,&T)) { for(k=0;k<=M;k++) { for(i=1;i<=N;i++) { if(i==P+k||P==i+k) dp[k][i]=1; else dp[k][i]=0; } } for(k=1;k<=M;k++) //一定要k循坏在外层，否则会出错 { for(i=1;i<=N;i++) { if(i<=P+k||P<=i+k) { if(i==1) dp[k][i]=dp[k-1][i+1]; else if(i==N) dp[k][i]=dp[k-1][i-1]; else dp[k][i]=dp[k-1][i-1]+dp[k-1][i+1]; } } } printf("%d\n",dp[M][T]); } return 0; }
转载地址：http://ubdci.baihongyu.com/