POJ 2229 Sumsets（基础dp）

秒速五厘米 2022-06-07 05:45 167阅读 0赞

Sumsets

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;200000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;20137</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;7870</td> 
  </tr> 
 </tbody> 
</table>

Description

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:   
  
1) 1+1+1+1+1+1+1   
2) 1+1+1+1+1+2   
3) 1+1+1+2+2   
4) 1+1+1+4   
5) 1+2+2+2   
6) 1+2+4   
  
Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

Input

A single line with a single integer, N.

Output

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample Input

7

Sample Output

6

AC代码：

思路：i是奇数 dp[i] = dp[i-1], i是偶数 dp[i] = dp[i-1]+dp[i/2],也可以算一道递推的题目吧

#include <iostream>  
    #include <cstdio>   
    using namespace std;  
    #define maxn 1000005  
    #define INF 1000000000  
      
    int dp[maxn];    
    void solve()  
    {   
        dp[0] = 1;  
        for(int i = 1; i < maxn; i++)  
        {  
            if(i % 2 != 0) dp[i] = dp[i-1];     //
            else dp[i] = ( dp[i-1] + dp[i/2] ) % INF;  
        }  
    }    
    int main()  
    {  
        int n;  
        solve();  
        while(scanf("%d" , &n) != EOF)  
        {  
            printf("%d\n" , dp[n]);  
        }
        return 0;  
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，167人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3254-Corn Fields【基础状压DP】

*描述** 农夫John已经购买组成一个新茂盛矩形牧场*中号*由*Ñ*（1≤ *m*≤12; 1≤ *ñ* ≤12）平方包裹。他想在一些广场上为奶牛种一些美味的玉米。遗...

野性酷女/ 2024年04月20日 09:15/ 0 赞/ 68 阅读

相关 POJ-3176 Cow Bowling【基础DP】

Cow Bowling <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

刺骨的言语ヽ痛彻心扉/ 2022年09月24日 06:25/ 0 赞/ 150 阅读

相关 Poj 2549 Sumsets (3Sum问题)

题意：给出一个数集，问其中是否存在a,b,c,d满足a+b+c=d，输出最大的d 理论学习：http://blog.csdn.net/doc\_sgl/article/det

灰太狼/ 2022年08月25日 15:55/ 0 赞/ 177 阅读

相关 POJ1163DP

题意和解析，看代码最后部分 include <iostream> include <cstdio> include <cmath> using

淡淡的烟草味﹌/ 2022年08月18日 00:40/ 0 赞/ 34 阅读

相关 Sumsets poj 2229 c++

Sumsets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 16:37/ 0 赞/ 58 阅读

相关 poj 2229 动态规划

怼烎@/ 2022年08月03日 14:47/ 0 赞/ 119 阅读

相关 POJ 2229 Sumsets（基础dp）

Sumsets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

秒速五厘米/ 2022年06月07日 05:45/ 0 赞/ 168 阅读

相关 POJ 2229 Sumsets————（完全背包 or 规律）

Sumsets Time Limit: 2000MS Memory Limit: 200000K Total Submissions: 23184 Accepted:

男娘i/ 2022年05月18日 04:36/ 0 赞/ 157 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 327 阅读

相关【dp】POJ-1050

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大. 首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。因为是连续若干个自然数的和，那前面的某个数字取

淩亂°似流年/ 2021年12月05日 13:09/ 0 赞/ 264 阅读