洛谷P1028数的计算

https://www.luogu.org/problemnew/show/P1028

只用递归会超时，需要用递归型动规，用一个数组保存已经算过的值，避免重复计算。

求数字为n的方案数的最优子结构为：求数字从1到n/2的方案数之和再加上这个数字本身，即fn=f1+f2+...+f(n/2)+1，

边界为：1的符合条件的方案数只有它自己,即f1=1.

例：

f(6)=f(1)+f(2)+f(3)+1=1+2+2+1=6.

f1=1,f2=f1+1=1+1=2,f3=f1+1=1+1=2。

 #include<iostream>

 #include<cstring>

 using namespace std;

 //int cnt = 1;

 int dp[];

 int f(int n)//数字为n的方案数

 {

     if (n == )//1满足条件的只有它自己

     {

         dp[n] = ;

         return dp[n];

     }

     if (dp[n] != )

     {

         return dp[n];

     }

     int e = n / ;

     int sum = ;

     for (int i = ; i <= e; ++i)

     {

         sum += f(i);

     }

     dp[n] = sum + ;//不为1的方案数除了从1到n/2的方案数之和还得加上这个数字自己

     return dp[n];

 }

 int main()

 {

     int n;

     memset(dp, , sizeof(dp));

     cin >> n;

     cout << f(n)<< endl;

     return ;

 }

巴特西

洛谷P1028数的计算

https://www.luogu.org/problemnew/show/P1028

最新文章

热门文章