头像

Wyz0823




离线:19分钟前


最近来访(33)
用户头像
歪比巴卜_62
用户头像
ylz
用户头像
yxᴄ
用户头像
艾伦_0
用户头像
yxc的小迷妹
用户头像
Sma10
用户头像
123_34
用户头像
谦言万语
用户头像
花与山川
用户头像
interesting_soul
用户头像
Unlimited
用户头像
啥也不会hh
用户头像
阿缘


Wyz0823
47分钟前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

//最长上升子序列  f[i] = max(f[i], f[j] + 1)
//最大上升子序列和 f[i] = max(f[i], f[j] + a[i])

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

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

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

Wyz0823
53分钟前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

typedef pair<int, int>PII;

int n;
PII q[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> q[i].first >> q[i].second;

    sort(q, q + n);//将下面一行从小到大排行序

    /*
    for(int i = 0; i < n; i ++)
        cout << q[i].first << " " << q[i].second << endl;
    */

    int res = 0;
    //上面一行中所选数字如果也是升序,不会出现相交
    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(q[i].second > q[j].second)
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);
    }

    //cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 482. 合唱队形

Wyz0823
1小时前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

//计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
//= 计算出可以形成的最长的合唱队伍是多少,用总数减去,就是最少需要出列的同学

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

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

    for(int i = n; i >= 1; i --)
    {
        g[i] = 1;
        for(int j = n; j > i; j --)
            if(a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res =  max(res, f[i] + g[i] - 1);

    cout << n - res << endl;

    return 0;
}



Wyz0823
2小时前

题目描述

(1)按编号递增的顺序来浏览 => 必须是子序列
(2)相邻两景点不能相同
(3)一但开始下降就不能上升

目标:求最大能浏览的景点数


C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    //预处理升序和降序的最长子序列

    //升序   
    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    //降序(从尾到头遍历求一遍)
    for(int i = n; i >= 1; i --)
    {
        g[i] = 1;
        for(int j =n; j > i; j --)
            if(a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    //开始下山点从1~n依次遍历,选出最大值
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i] + g[i] - 1);//-1:第i点算了两次

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 1014. 登山

Wyz0823
2小时前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

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

    for(int i = n; i >= 1; i --)
    {
        g[i] = 1;
        for(int j =n; j > i; j --)
            if(a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i] + g[i] - 1);

    cout << res << endl;

    return 0;
}



Wyz0823
4小时前

题目描述

题目给定一个长度为 nn 的一维数组 w[n]w[n],表示每个楼房的高度

怪盗基德可以选定任意一个楼房,作为他的起始位置

他可以选择向左或向右出发直到边界,途中不能改变方向

题目要求我们找出一条路径,使得他飞行的路线上,经过的高度递减的楼房子序列长度最大

输出该子序列的长度


C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N];//存第i个建筑的高度
int f[N];//以a[i]结尾的最长上升子序列

int main()
{
    int T;
    cin >> T;
    while(T --)//多组数据
    {
        cin >> n;
        for(int i = 1; i <= n; i ++)
            cin >> a[i];

        int res = 0;//可以飞的最远距离

        //任意地点可以的往更低地方跑:正向求上升子序列的和
        //任意方向:正向,反向都求一次

        //正向求解
        for(int i = 1; i <= n; i++)
        {
            f[i] = 1;//本身也算1
            for(int j = 1; j < i; j ++)
                if(a[i] > a[j])//上升子序列,必须小于当前的数
                    f[i] = max(f[i], f[j] + 1);

            res = max(res, f[i]);
        }

        //反向求解
        for(int i = n; i >= 1; i --)//n ~ 1
        {
            f[i] = 1;
            for(int j = n; j > i; j --)//n ~ i - 1
                if(a[i] > a[j])//前面n ~ i - 1已经被更新了
                    f[i] = max(f[i], f[j] + 1);

            res = max(res, f[i]);
        }

        cout << res << endl;
    }

    return 0;
}



Wyz0823
4小时前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N];
int f[N];//以a[i]结尾的最长上升子序列

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n;
        for(int i = 1; i <= n; i ++)
            cin >> a[i];

        int res = 0;
        //正向求解
        for(int i = 1; i <= n; i++)
        {
            f[i] = 1;//本身也算1
            for(int j = 1; j < i; j ++)
                if(a[i] > a[j])//上升子序列,必须小于当前的数
                    f[i] = max(f[i], f[j] + 1);

            res = max(res, f[i]);
        }

        //反向求解
        for(int i = n; i >= 1; i --)
        {
            f[i] = 1;
            for(int j = n; j > i; j --)
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);

            res = max(res, f[i]);
        }

        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 275. 传纸条

Wyz0823
6小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;

int n, m;
int w[N][N];
int f[N + N][N][N];//f[k][i][j]存储从(1,1)到(i,k -1),从(1,1)到(j,k - j)两天路线的最大值

int main()
{
    cin >> n >> m;

    for(int i  = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> w[i][j];

    /*(i,j)的取值必须再给定范围之内
    1 <= x1 <= n
    1 <= k - x1 <= m
    可推导出
    x1 <= k - 1  x1 <= n
    x1 >= k - m  x1 >=1
    */
    for(int k = 2; k <= n + m; k ++)
        for(int x1 = max(k - m, 1); x1 <= min(k - 1, n); x1 ++)
            for(int x2 = max(k - m, 1); x2 <= min(k - 1, n); x2 ++)
            {
                int t = w[x1][k - x1];
                if(x1 != x2) t += w[x2][k - x2];
                //用两重循环简化
                for(int a = 0; a <= 1; a ++)
                    for(int b = 0; b <= 1; b ++)
                        f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t);
            }

    cout << f[n + m][n][n] << endl;

    return 0;
}



Wyz0823
1天前

题目描述

设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:

2.gif

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。

在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。

样例

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

结果

67


C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N + N][N][N];
//f[k][i1][i2]表示所有从(1,1)(1,1)分别走到f(i1,j1)f(i1,j2)的路径上数和的最大值
// k = i1 + j1 = i2 + j ,k为横纵坐标长度之和,j1 = k - i1, j2 = k - i2

int main()
{
    cin >> n;

    int a, b, c;
    while(cin >> a >> b >> c, a || b || c) w[a][b] = c;//输入,以输入三个零结束

    //三重循环,k(横纵坐标长度之和)从2(起始点至少为2)到2n(横纵坐标之和的最后一点为2n)
    //i1(第一条路径所到点的横坐标),i2(第二条路径所到点的横坐标)从1到n(横坐标的最后为n)
    for(int k = 2; k <= n + n; k ++)
        for(int i1 = 1; i1 <= n; i1 ++)
            for(int i2 = 1; i2 <= n; i2 ++)
            {
                //j1第一条路径所到点的纵坐标,j2第二条路径所到点的纵坐标
                int j1 = k - i1, j2 = k - i2;

                //必须合法,在所给范围之内
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int t = w[i1][j1];

                    //当第一条路径与第二条路径所走到的点相同的时候总数为w[i1][j1] + 0
                    //不相同时加上第二条路径所到的点
                    if(i1 != i2)t += w[i2][j2];

                    //&x:当后面x的值发生改变的时候,f[k][i1][i2]的值也会发生改变,减少代码
                    int &x = f[k][i1][i2];

                    //第一条路径与第二条路径走的方向都是从上往下
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);

                    //第一天路径的方向是从上往下,第二条路径的方向是从左往右
                    x = max(x, f[k - 1][i1 - 1][i2] + t);

                    //第一天路径的方向是从左往右,第二天路径的方向是从上往下
                    x = max(x, f[k - 1][i1][i2 - 1] + t);

                    //第一条与第二条路径的方向都是从左往右
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }

    cout << f[n + n][n][n] << endl;

    return 0;
}



活动打卡代码 AcWing 1027. 方格取数

Wyz0823
1天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N + N][N][N];
//f[k][i1][i2]表示所有从(1,1)(1,1)分别走到f(i1,j1)f(i1,j2)的路径上数和的最大值
// k = i1 + j1 = i2 + j ,k为横纵坐标长度之和,j1 = k - i1, j2 = k - i2

int main()
{
    cin >> n;

    int a, b, c;
    while(cin >> a >> b >> c, a || b || c) w[a][b] = c;

    //三重循环,k(横纵坐标长度之和)从2(起始点至少为2)到2n(横纵坐标之和的最后一点为2n)
    //i1(第一条路径所到点的横坐标),i2(第二条路径所到点的横坐标)从1到n(横坐标的最后为n)
    for(int k = 2; k <= n + n; k ++)
        for(int i1 = 1; i1 <= n; i1 ++)
            for(int i2 = 1; i2 <= n; i2 ++)
            {
                int j1 = k - i1, j2 = k - i2;//j1第一条路径所到点的纵坐标,j2第二条路径所到点的纵坐标
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)//必须合法,在所给范围之内
                {
                    int t = w[i1][j1];
                    //当第一条路径与第二条路径所走到的点相同的时候总数为w[i1][j1] + 0
                    //不相同时加上第二条路径所到的点
                    if(i1 != i2)t += w[i2][j2];
                    //&x:当后面x的值发生改变的时候,f[k][i1][i2]的值也会发生改变,减少代码
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);//第一条路径与第二条路径走的方向都是从上往下
                    x = max(x, f[k - 1][i1 - 1][i2] + t);//第一天路径的方向是从上往下,第二条路径的方向是从左往右
                    x = max(x, f[k - 1][i1][i2 - 1] + t);//第一天路径的方向是从左往右,第二天路径的方向是从上往下
                    x = max(x, f[k - 1][i1][i2] + t);//第一条与第二条路径的方向都是从左往右
                }
            }

    cout << f[n + n][n][n] << endl;

    return 0;
}