小记:一开始自己是用的dp,dp数组定义也对了。但是就是状态转移方程少加一个步。然后看了一下discuss,别人用了dp,更多的是母函数,不过我一开始用的是dp那么就用dp解。然后看了一眼别人的dp,发现和自己定义的是一样的,所以就自己继续想状态转移方程,终于理解出来了。
思路:母函数模板题,我的blog里可看讲解,dp,这里先讲讲dp,
dp[i][j]表示对数i,用不大于j的数组成i的 种数
状态转移方程:
对于i<j,dp[i][j] = dp[i][i]
对于i==j,dp[i][j] = 1 + dp[i][j-1]
对于i>j,dp[i][j] = dp[i-j][j] + dp[i][j-1]
主要的一个方程就是i>j时的。
dp[i][j] 包括两个部分,
第一部分就是不包括j且小于用小于j的数组成i的种数
第二部分就是包括了一个j,那么我们剩下的还要凑齐的就是i-j这个数,而用来凑的数不能大于j,
所以,第一部分的种数就是dp[i-j][j],第二部分的种数即为dp[i][j-1]
例:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
dp[4][3] = dp[4][2] + dp[1][3]
通过上面理解,dp[i][j]一部分是包括了j的和不包括j的两部分
初始化,dp[0][i] = dp[i][0] = 0
dp[1][i] = dp[i][1] = 1
dp代码:
#include <iostream> #include <cstdio> using namespace std; const int MAX_ = 130; int f[MAX_][MAX_]; void init(){ for(int i = 1;i < MAX_;++i){ f[0][i] = 0; f[i][0] = 0; f[i][1] = 1; f[1][i] = 1; } for(int i = 1; i < MAX_; ++i){ int cnt = 0; for(int j = 1; j < MAX_; ++j){ if(i < j)f[i][j] = f[i][i]; else if(i == j)f[i][j] = 1 + f[i][j-1]; else { f[i][j] = f[i-j][j] + f[i][j-1]; } } } } int main(){ //freopen("f:\\out.txt","w",stdout); long long n; init(); while(cin>>n){ cout<<f[n][n]<<endl; } return 0; }
母函数模板直接提交,直接A,改都不用改:
#include <iostream> using namespace std; // Author: Tanky Woo // www.wutianqi.com const int _max = 10001; // c1是保存各项质量砝码可以组合的数目 // c2是中间量,保存没一次的情况 int c1[_max], c2[_max]; int main() { //int n,i,j,k; int nNum; // int i, j, k; while(cin >> nNum) { for(i=0; i<=nNum; ++i) // ---- ① { c1[i] = 1; c2[i] = 0; } for(i=2; i<=nNum; ++i) // ----- ② { for(j=0; j<=nNum; ++j) // ----- ③ for(k=0; k+j<=nNum; k+=i) // ---- ④ { c2[j+k] += c1[j]; } for(j=0; j<=nNum; ++j) // ---- ⑤ { c1[j] = c2[j]; c2[j] = 0; } } cout << c1[nNum] << endl; } return 0; }