【动态规划】POJ 2229
题目地址:http://poj.org/problem?id=2229
题目大意
大致题意是,一个数N能有几种拆分方式,拆分的数字必须是2的幂。
思路
刚开始用母函数试了一下,果断超时2333。。。
还是动态规划找下规律吧。
首先考虑N为奇数,奇数的话必然都是1开头,例如7
- 1+1+1+1+1+1+1 = 7
- 1+1+1+1+1+2
- 1+1+1+2+2
- 1+1+1+4
- 1+2+2+2
- 1+2+4
把所有的1去掉,即
- 1+1+1+1+1+1 = 6
- 1+1+1+1+2
- 1+1+2+2
- 1+1+4
- 2+2+2
- 2+4
则此时和为6,也就是说,若N为奇数,则拆分数和N-1(偶数)的拆分数一样。
若N为偶数,则必然有两种情况:1开头和2开头,例如上面的6。而1开头的拆分数和N-1(奇数)的拆分数加上2开头的拆分数。将所有2开头的拆分数除以2,则数量和N/2的拆分数一致。例如6以2开头的拆分数(就是6/2=3的拆分数):
- $2+2+2 => 1+1+1 = 3$
- $2+4 => 1+2$
综上所述,有$dp[N] = dp[N-1] + dp[N\%2==0?N/2:0]$
AC代码
/*************************************************************************
> File Name: 2229.cpp
> Author: Netcan
> Blog: http://www.netcan.xyz
> Mail: 1469709759@qq.com
> Created Time: 2015-09-20 日 15:42:21 CST
************************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int N;
int a[1000005];
void solve() {
a[1] = 1;
a[2] = 2;
for(int i=3; i<=N; ++i)
a[i] = (a[i-1] + (i%2==0 ? a[i/2] : 0)) % 1000000000;
cout << a[N] << endl;
}
int main()
{
#ifdef Oj
// freopen(".in", "r", stdin);
#endif
cin.sync_with_stdio(false);
cin >> N;
solve();
return 0;
}
- 本文标题:【动态规划】POJ 2229
- 本文字数:445
- 本文作者:Netcan
- 发布时间:2015年09月20日 - 16时06分
- 最后更新:2015年09月20日 - 16时06分
- 原始链接:http://www.netcan666.com/2015/09/20/【动态规划】POJ-2229/
- 版权声明:"署名-非商用-相同方式共享 3.0"转载请保留原文链接及作者。
- 打赏: