POJ 2229 Sumsets（基础dp）

秒速五厘米 2022-06-07 05:45 150阅读 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 条评论，150人围观）

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

相关阅读

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

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

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

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

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

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

相关 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 赞/ 169 阅读

相关 POJ 2955 区间dp

题意：求括号匹配的最大长度思路：简单区间dp，令dp\[i\]\[j\] 为区间（i,j）之间的最大匹配长度。这样dp\[i\]\[j\] = max( dp\[i

Love The Way You Lie/ 2022年08月18日 11:55/ 0 赞/ 199 阅读

相关 POJ 2229 Sumsets（基础dp）

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

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

相关 poj 2253（区间DP）

[原题][Link 1] 思路：求所有路径中最大跳跃距离的最小值，很诡异的是输出答案如果用G++，.3lf%格式会出错，c++可以过 include<cstdio

男娘i/ 2022年06月04日 03:05/ 0 赞/ 217 阅读

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

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

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

相关 poj3252（数位dp）

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

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

相关【dp】POJ-1050

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

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

相关 poj1037（计数dp）

题意：给定n个数字，规定一种 cute 排序：序列中的数字大小为严格的波浪形，即 a\[0\] > a\[1\] < a\[2\] > a\[3\] < .... 或者 a\

àì夳堔傛蜴生んèń/ 2021年11月29日 14:42/ 0 赞/ 322 阅读