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 (577) ysjjovo 2011-03-13 21:44:22
  • Re:brute force (32) ysjjovo 2011-03-13 21:45:01