POJ - 2229 Sumsets （动态规划）

本文主要是介绍POJ - 2229 Sumsets （动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接

很巧妙的一道题，需要找到奇偶数的递推关系。

1、当N为奇数时：d[N] = d[N-1];

2、当N为偶数时：d[N] = d[N-1] +d[N/2];

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 1000001;
int d[MAX_N];
int main()
{int N;scanf("%d", &N);d[1] = 1;d[2] = 2;for(int i = 3; i <= N; i++)if(i & 1)d[i] = d[i-1];else d[i] = (d[i-1] + d[i/2]) % 1000000000;printf("%d\n", d[N]);return 0;
}

另一种动态规划的做法：

d[i][j]  表示前i个数，总和为j，符合题意的个数。

类似于完全背包，相对于前一种做法，所取的数可以不局限于是2的幂。

但是时间复杂度不如前者，这里是O（nlogn），在POJ要1047ms，而前者只要47ms。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAX_N = 1000001, MAX = 1E9;
int d[MAX_N];
int main()
{int N;scanf("%d", &N);int m = log(N) / log(2);d[0] = 1;for(int i = 0; i <= m; i++)for(int j = (1<<i); j <= N; j++)d[j] = (d[j] + d[j-(1<<i)]) % MAX;printf("%d\n", d[N]);return 0;
}

这篇关于POJ - 2229 Sumsets （动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---