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

• Re:brute force (32) ysjjovo 2011-03-13 21:45:01