==>原题链接

题目概述

总时间为n，有m个时间段，每个段有一个权值w，让你选一些不冲突的时间段给奶牛挤奶，得到最高的总权值。注意每次挤牛奶要有一个休息时间r，需要做一下小处理。

思路

DP。区间DP。DP的特点是 对状态的记录 和 传递。
变换了DP类型还是有点不适应，其实思路异乎寻常的简单。

dp[i] = max(dp[i], dp[j] + num[i].w);

dp[i]表示选取前i段，其中包含第i段的最大权值。那么就是枚举i段之前的那些空余时间可满足的段。

以前i我们已经很熟悉了，是利用传递阶段信息的办法得出前一个阶段的最优结果。必须包含i段使得整个式子能枚举到每一种情况但不重样，是出于有序性的一种合理的强制规定，你可以规定别的，但是这样规矩减少维度，同时很方便，应该熟练。

代码

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef struct
{
    int st, en, w;
} DATA;

DATA num[1000+10];
int dp[1000000+10];

bool cmp(DATA a, DATA b);

int main()
{
    int i, j;
    int n, m, r, ans = 0;

    freopen("3616.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &r);
    n += r;

    for (i = 0; i < m; i++)
    {
        scanf("%d%d%d", &num[i].st, &num[i].en, &num[i].w);
        num[i].en += r;
    }

    sort(num, num + m, cmp);

    for (i = 0; i < m; i++)
    {
        dp[i] = num[i].w;
    }

    for (i = 0; i < m; i++)
    {
        for (j = 0; j < i; j++)
        {
            if(num[i].st >= num[j].en)
            {
                dp[i] = max(dp[i], dp[j] + num[i].w);
            }
        }

        ans = max(ans, dp[i]);
    }

    printf("%d\n", ans);


    return 0;
}

bool cmp(DATA a, DATA b)
{
    if (a.st == b.st)
    {
        return a.en < b.en;
    }
    else
    {
        return a.st < b.st;
    }
}

==>原题链接

题目概述

FJ在两棵苹果树下等着苹果，FJ开始在树1下，给出每个时刻苹果在哪棵树上掉下来，最多能移的次数，求最多能得到的苹果数。

思路

DP。

dpi = max(dpi-1, dpi-1) + rec;

表示前i时刻，移动j次，最多能得到的苹果数，他取决于 这一时刻是否移动 和 移动后是否取得此刻的苹果。

最后只要枚举各个移动次数，可取得最大值 比较输出即可。

（完整的思路☂，赞~）

“枚举 i个时刻 不同次数”，比较，新技能GET

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[1000+10][30+10],
    num[1000+10];
int main()
{
    int i, j;
    int n, w, rec, ans = 0;

    freopen("2385.in", "r", stdin);
    scanf("%d%d", &n, &w);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
    }

    memset(dp, 0, sizeof(dp));

    for (i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i-1][0] + (num[i] & 1);
        for (j = 1; j <= i && j <= w; j++)
        {
            if (1 + j % 2 == num[i])
            {
                rec = 1;
            }
            else
            {
                rec = 0;
            }
            //rec = (1 + j & 1 + num[i]) & 1 ? 1:0;
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + rec;
        }
    }

    for (j = 1; j <=  w; j++)
    {
        ans = max(ans, dp[n][j]);
    }

    printf("%d\n", ans);


    return 0;
}

==>原题链接

题目概述

把一个数字n划分为 二的次幂 加和的形式，问共有多少种不同的分法。

思路

一开始企图记忆化搜索后来发现思路是错误的，可能会导致重复。

反例：

dp(5) = dp(3) + dp(2) = (1 + 2) + 2

  = dp(4) + dp(1) = (2 + 2) + 1

但这两种显然是同一种。

正确的思路是 为了避免重复，由于2是一个特别的数字——偶数的基，我们尝试将n的加和算式分为只有偶数相加 和 奇偶相加两种情况（纯奇数相加只有1+1+1...的情况，视作奇偶混合的）。

如果n是奇数，那么只能是奇偶混合相加，dp[n] = dp[n-1]，即在n-1的结果上再加1，与n-1的值无异
如果n是偶数，那么可以有奇偶混合 和 纯偶数相加两种，dp[n] = dp[n-1] + dp[n/2] 其中dp[n-1]易理解，dp[n/2]则是为了保证所得结果dp[n/2]为只有偶数的情况，因为无论n/2是否为偶数，n均为偶数。我们按照这样的划分可以保证既不重复，又不缺漏。

实际上这样的划分很具有题目的特性，并不保证是通用思路。更多的依靠列出大量的式子枚举找规律推倒得出递推。
这启发我们在没有思路的情况下大可枚举找规律，找出突破。

代码

#include <stdio.h>
#include <string.h>

const int N = 1000000000;
int dp[1000000 + 10];

int main()
{
    int i;
    int n;

    memset(dp, 0, sizeof(dp));
    freopen("2229.in", "r", stdin);
    scanf("%d", &n);
    dp[1] = 1;
    dp[2] = 2;

    for (i = 3; i <= n; i++)
    {
        if (i & 1)
        {
            dp[i] = dp[i-1] % N;
        }
        else
        {
            dp[i] = dp[i-1] % N + dp[i/2] % N;
        }
    }

    printf("%d\n", dp[n]);

    return 0;
}

==>原题链接

题目概述

最经典的DP，数塔。

思路

DP 或 记忆化搜索 或 从下到上的贪心。

注释的代码为标准DP，未注释部分为记忆化搜索。
记忆化搜TLE了，让小伙伴调了大半天，在此感谢Smile同学。

警示

TLE的原因是初始化ans[]均为0，而int dp()中 >0 才会返回值否则递归搜索，结果全0的数据要全部递归一遍几十个就超时了。
正确的姿势是 初始化为-1，>0 即调用。就不会出这个问题了，因为数字中如果有小于0的会让结果变小，不可能max到。

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 350 + 10;
int num[N][N];

/*
int dp[N][N];

int main()
{
    int i, j;
    int n, ans = 0;

    freopen("3176.in", "r", stdin);
    memset(dp, 0, sizeof(dp));
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            scanf("%d", &num[i][j]);
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + num[i][j];

            if (dp[i][j] > ans)
            {
                ans = dp[i][j];
            }
        }
    }

    printf("%d\n", ans);


    return 0;
}
*/


int n;
int ans[N][N];

int dp(int i, int j);

int main()
{
    int i, j;
    int res = 0;

    freopen("3176.in", "r", stdin);
    memset(ans, -1, sizeof(ans));
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            scanf("%d", &num[i][j]);
        }
    }

    res = dp(1, 1);

    printf("%d\n", res);
    return 0;
}

int dp(int i, int j)
{
    if (i > n)
    {
        return 0;
    }

    if (ans[i][j] >= 0)
    {
        return ans[i][j];
    }

    ans[i][j] = max(dp(i + 1, j), dp(i + 1, j + 1)) + num[i][j];

    return ans[i][j];
}

dp[i]表示长度为i＋１的上升子序列的末尾元素的值，迭代后为＝＝＞最小值

#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX = 100000000;
void solve();

const int n = 5;
int a[5] = {4, 2, 3, 1, 5};
int dp[5];

int main()
{
    solve();
    return 0;
}

void solve()
{
    int i;
    
    fill(dp, dp + n, MAX);
    for (i = 0; i < n; i++)
    {
        *lower_bound(dp, dp + n, a[i]) = a[i];
    }
    printf("%d\n", lower_bound(dp, dp + n, MAX) - dp);
}