HDU - 2709 Sumsets 【递推】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2709

题意

给出一个数N 要求有多少种方式求和能够等于N

加的数必须是 2的幂次

思路

首先可以想到的是

如果 N 是奇数的话

那么到达N 的方法数就是到达 N - 1 的方法数

因为就相当于把所有到达N-1 的方法数都再 + 1

如果 N 是偶数的话

就有两种情况

0.分解的数字中至少有两个1 那么 dp[n] = 1 + 1 + dp[n - 2]

1.分解的数字中没有1 也就是说是由dp[n - 2] 中每个分解方式中的数字都*2 就是 n

所以 dp[n] = dp[n - 2] + dp[n / 2]

AC代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<list>

#include<stack>

#include <queue>

#define CLR(a, b) memset(a, (b), sizeof(a))

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int maxn = 1e6 + 5;

const int MOD = 1e9;

ll dp[maxn];

void init()

{

    dp[0] = 1;

    for(int i=1;i<maxn;++i)

    {

        if(i&1) dp[i]=dp[i-1];

        else dp[i]=(dp[i-2]+dp[i/2]) % MOD;

    }

}

int main()

{

    init();

    int n;

    while (~scanf("%d", &n))

    {

        printf("%lld\n",dp[n]%MOD);

    }

}

思路二

可以枚举式子中最大的那位是多少

比如最大的那位是 1

dp[1] = 1;

那么

dp[n] = dp[n - 1]

此时表示的状态是每个到N的方式组成的数字中只有1

最大位是2

那么

dp[n] += dp[n - 2]

因为我们是按照最大数枚举上去的

而不是按照之前的状态转移的

比如最大数是2

那么 dp[n] 就要加上 dp[n - 2] dp[n - 2] 表示最大数是2 来到达n - 2 的方式总数

而不是到达 n - 2 的所有方式

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e6 + 5;

const int MOD = 1e9;

int binary[25];

int dp[maxn];

void init()

{

    CLR(binary, 0);

    CLR(dp, 0);

    binary[0] = 1;

    dp[0] = 1;

    for (int i = 1; i < 25; i++)

        binary[i] = binary[i - 1] * 2;

    for (int i = 0; i < 25 && binary[i] < maxn; i++)

    {

        for (int j = binary[i]; j < maxn; j++)

        {

            dp[j] += dp[j - binary[i]];

            dp[j] %= MOD;

        }

    }

}

int main()

{

    init();

    int n;

    while (~scanf("%d", &n))

        cout << dp[n] % MOD << endl;

}

巴特西

HDU - 2709 Sumsets 【递推】

最新文章

热门文章