学步园

brute force:

#include<iostream><br /> using namespace std;<br /> int ans,curCnt;<br /> int curNumber;<br /> int cnt;<br /> void work(int k,int cur){//k<=cnt-1,cur<=curNumber<br /> if(k==cnt-1){<br /> if(curNumber>=cur&&curNumber<=cur+9)curCnt++;// ÕâÒ»¾äshit!!!<br /> }<br /> else{<br /> if(cur+(cnt-k)*9<curNumber)return;<br /> int i;<br /> for(i=0;i<10;i++){<br /> if(cur+i>curNumber)return;<br /> work(k+1,cur+i);<br /> }<br /> }<br /> }</p> <p>int main(){<br /> int n;<br /> cin>>n;<br /> if(n&1){<br /> cout<<0<<endl;<br /> return 0;<br /> }<br /> ans=2;<br /> int i;<br /> cnt=n/2;<br /> for(i=1;i<cnt*9;i++){<br /> curNumber=i;<br /> curCnt=0;//0,max<br /> work(0,0);<br /> ans+=(curCnt*curCnt);<br /> }<br /> cout<<ans<<endl;<br /> return 0;<br /> }<br />

dp[n][s]为n个数字和为s的方案数
则转移方程：dp[n+1][s+i]+=dp[n][s]   -1<i<10
代码：
#include<iostream><br /> using namespace std;<br /> int main(){<br /> int n;<br /> cin>>n;<br /> if(n&1){<br /> cout<<0<<endl;<br /> return 0;<br /> }<br /> int i,j,k;<br /> int dp[6][9*5+1];<br /> int max=9;<br /> memset(dp,0,sizeof(dp));<br /> fill(dp[1],dp[1]+10,1);<br /> for(i=1;i<n/2;i++){<br /> for(j=0;j<=max;j++){<br /> for(k=0;k<=9;k++){<br /> dp[i+1][j+k]+=dp[i][j];<br /> }<br /> }<br /> max+=9;<br /> }<br /> int ans=0;<br /> for(j=0;j<=max;j++){<br /> ans+=(dp[i][j]*dp[i][j]);<br /> }<br /> cout<<ans<<endl;<br /> return 0;<br /> }

结果悲剧了
brute force:oMS
dp:16MS!