1.Max Sum Plus Plus
$给你一个数m和一个数组 让你求出由m个子段和能组成的最大值，并且每个数字不能重复使用$

首先 f[i][j] 表示由前i个子段构成且包含 a[j] 的集合 属性是max
那么枚举a[j]的时候就有两个选择 1.将它加入我们当前的第i个子段 2.不将他将入当前的第i个子段
状态转移方程是 f[i][j] = max(f[i-1][k] + a[j], f[i][j-1] + a[j]);(i < k < j) 
那么时间复杂度是O(m*n*n)的 T！

优化：
我们可以用一个pre数组每次去存前i-1个子段的状态 用f数组记录当前的状态
那么每次转移就可以变成 f[j] = max(f[j-1], pre[j-1]) + a[j]
然后用一个变量维护当前层的以a[j]结尾的最大值 然后更新 pre 即可

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

const int N = 1e6 + 10;

int f[N], pre[N];
int n, m;
int a[N];

int main()
{
    while(~scanf("%d%d",&m,&n))
    {

        for(int i=1;i<=n;i++)
        {
            cin >> a[i];
            f[i] = 0, pre[i] = 0;
        }

        int t = 0;

        for(int i=1;i<=m;i++)
        {
            t = -1e9;//由前i子段构成且含a[j]的最大值
            //因为状态是前i个子段所以循环j的时候要从i开始不然只有1个数怎么组成两个子段呢
            for(int j=i;j<=n;j++)
            {
                f[j] = max(pre[j-1], f[j-1]) + a[j];

                pre[j-1] = t;
                t = max(t, f[j]);
            }
        }

        cout << t << endl;
    }

}

2.Ignatius and the Princess IV
桶排序

 #include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

const int N = 1e6 + 10;

int n;
int cnt[N];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++)
        {
            int x;cin >> x;
            cnt[x] ++;
        }

        int t = (n+1)/2;

        for(int i=1;i<=999999;i++)
            if(cnt[i] >= t) cout << i;

        cout << endl;

    }

}

3.Monkey and Banana
$最长上升子序列的变形 每块砖能有不同摆法 都存进结构体即可 然后从小到大把长、宽排序$
$f[i]是以第i块砖为底部能到达的最大高度$
$状态转移为f[i] = max(f[i],f[j] + g[i].w) 满足条件即可转移$

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

const int N = 300;

int f[N], n;//以第i块砖为底部达到的最大高度
struct node
{
    int l, r, w;
    bool operator < (const node &t) const{
        if(t.l != l) return l < t.l;
        return r < t.r;
    }
}g[N];

int main()
{
    int t = 0;
    while(cin >> n, n)
    {
        t++;
        int cnt = 0;
        memset(f,0,sizeof f);

        for(int i=0;i<n;i++)
        {
            int l,r,w;
            cin >> l >> r >> w;
            g[cnt++] = {l,r,w};
            g[cnt++] = {l,w,r};
            g[cnt++] = {r,w,l};
            g[cnt++] = {r,l,w};
            g[cnt++] = {w,l,r};
            g[cnt++] = {w,r,l};
        }

        sort(g,g+cnt);
        int res = 0;

        for(int i=0;i<cnt;i++)
        {
            f[i] = g[i].w;
            for(int j=0;j<i;j++)
            {
                if (g[i].l > g[j].l && g[i].r > g[j].r)
                {
                    f[i] = max(f[i], f[j] + g[i].w);
                }
            }
            res = max(res, f[i]);
        }

        printf("Case %d: maximum height = %d\n",t,res);
    }

}

Super Jumping! Jumping! Jumping!
$裸的最长上升子序列$

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

const int N = 1010;

int f[N], n; 
int a[N];

int main()
{
    int t = 0;
    while(cin >> n, n)
    {
        memset(f,0,sizeof f);

        for(int i=0;i<n;i++) scanf("%d",a+i);

        int res = 0;
        for(int i=0;i<n;i++)
        {
            f[i] = a[i];
            for(int j=0;j<i;j++)
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + a[i]);
            res = max(res, f[i]);
        }

        cout << res << endl;
    }

}

$Help Jimmy$ Help jimmy
$f[i][0/1]表示从第i块砖，向左/右走最快到达地面的时间$
$那么只能从左or右转移$
$左：从左边跳下去，那么下一块砖的左边必须比当前砖左边靠左即坐标小于当前砖$
$右边必须大于当前砖，即左边大于$
$右边同理：下一块砖的左边比当前砖右边靠左，下一块砖右边比当前砖右边靠右$
$我们应该从最低层向上转移，刚开始是想着从上向下转移$
$但是这样没法处理最下面一层与地面见超过限制的情况$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int N = 1010 + 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;

int dp[N][2];
int n, x, y, limit;
struct node
{
    int x,y,h;
    bool operator < (const node& t) const {
        return h < t.h;
    }
}g[N];

void left(int i)
{
    int k = i - 1;//第i块木板下
    while (k>0 && g[i].h-g[k].h <= limit)
    {
        if(g[i].x>=g[k].x&&g[i].x<=g[k].y)
        {
            int t = g[i].h-g[k].h;
            int l = g[i].x - g[k].x;
            int r = g[k].y - g[i].x;
            dp[i][0] = min(l+dp[k][0], r+dp[k][1]) + t;
            return ;
        }
        else k --;
    }

    if(g[i].h <= limit) dp[i][0] = g[i].h;
    else dp[i][0] = inf;
    return ;

}

void right(int i)
{
    int k = i - 1;//第i块木板下
    while (k>0 && g[i].h-g[k].h <= limit)
    {
        if(g[i].y>=g[k].x&&g[i].y<=g[k].y)
        {
            int t = g[i].h-g[k].h;
            int l = g[i].y - g[k].x;
            int r = g[k].y - g[i].y;
            dp[i][1] = min(l+dp[k][0], r+dp[k][1]) + t;
            return ;
        }
        else k --;
    }

    if(g[i].h <= limit) dp[i][1] = g[i].h;
    else dp[i][1] = inf;
    return ;
}

int main()
{
    int cases;
    cin >> cases;
    while (cases --)
    {
        memset(dp,0,sizeof dp);

        cin >> n >> x >> y >> limit;
        g[0].x = x, g[0].y = x, g[0].h = y;
        g[1].x = -20000, g[1].y = 200000, g[1].h = 0;

        for(int i=2;i<n+2;i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            g[i] = {a,b,c};
        }

        sort(g,g+2+n);

        // for(int i=0;i<=n+1;i++) cout << g[i].h << " ";
        // cout << endl;

        for(int i=1;i<=n+1;i++)
        {
            left(i);
            right(i);
        }

        cout << min(dp[n+1][0], dp[n+1][1]) << endl;
    }
    return 0;
}