4月3日

poj2229

题意：给定一个数，把它拆分成2的n次幂相加的形式，问有多少种方法，结果取后9位

分析：这道题目很有意思，可以把一个数i分成奇数和偶数的情况来讨论，当i是奇数时，i拆分以后的个数与i-1是一样的，而当i是偶数时，相当于将i-1加上一个1以后同时可以把两个1为一组进行合并，故为i-1与i/2的和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int mod=1000000000;
const int maxn=1001000;
int dp[maxn];
int n;
int main()
{
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            if(i%2)
                dp[i]=dp[i-1]%mod;
            else
                dp[i]=(dp[i-1]+dp[i/2])%mod;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
    return 0;
}

 poj2385

题意:牛在1,2两棵树之间接苹果，苹果总共落下t次，牛总共可在树之间走w次，问牛最多能吃到多少苹果，开始时牛在第一棵树下

分析:一个很经典的dp问题，这题要好好总结一下，开始我的思路有些问题，后来看了下题解之后有所领悟。跟上面一题一样，还是要分为奇数跟偶数两种情况来进行讨论，当牛走的次数为偶数时，在树1下，当牛走的次数为奇数时，在树2下。dp[i][j]记录牛在第i秒走了j次之后所吃苹果的最大值，那么也就是记录每一步走或者不走的最大值。显然dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])。因为i-1次只能走j步或者j-1步。用a[i]==j%2+1,来判断是否第几棵树。别忘了初始化。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int maxn=1010;
int dp[maxn][40];
int a[maxn];
int t,w;
int main()
{
    while(cin>>t>>w)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=t;i++)
            cin>>a[i];
        for(int i=1;i<=t;i++)    //初始化，表示一次都不走的情况
            dp[i][0]=dp[i-1][0]+(a[i]%2);
        for(int i=1;i<=t;i++)
        {
            for(int j=1;j<=w;j++)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+(a[i]==j%2+1);
        }
        cout<<dp[t][w]<<endl;
    }
    return 0;
}