根据题给信息，要看尽可能多的节目，我们就得尽可能的看持续时间短，且开始时间尽可能早的节目。

所以各个节目的权值可以设置为

 ，权值越小的优先级越高。这样就可以让相同持续时间但开始时间更早的节目排在前面。

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct node

{

    int Ti_s;
    int Ti_e;
    int Ti_d;
};


bool compare(node a, node b)
{
    return (a.Ti_d + a.Ti_s) < (b.Ti_d + b.Ti_s);
}
int main()

{
    int n;
    while (cin >> n && n != 0)
    {

        vector<node> v(n);

        for (int i = 0; i < n; i++)
        {
            cin >> v[i].Ti_s >> v[i].Ti_e;
            v[i].Ti_d = v[i].Ti_e - v[i].Ti_s;
        }
        sort(v.begin(), v.end(), compare);

        int count = 0;
        int curTime = -1;
        for (int i = 0; i < n; i++)
        {
            if (v[i].Ti_s >= curTime)
            {
                count++;
                curTime = v[i].Ti_e;
            }
        }
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()
{
    int m;
    cin >> m;
    // dp[i]表示走到第i级楼梯的方法数
    vector<int> dp(50, -1);
    dp[1] = 1;
    dp[2] = 1;

    for (int i = 3; i <= 50; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];

    }
    while (m--)

    {
        int n;
        cin >> n;
        cout << dp[n] << endl;
    }

    return 0;
}   

3. 简单斐波那契数列 （HDU2044）

根据所给输入确定起始点和边界条件，注意当b-a ≥ 46时，将会超出int的表示范围。

#include <iostream>

#include <vector>
using namespace std;


int main()
{


    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        if (a == b)
        {
            cout << 1 << endl;
            continue;
        }
        // dp[i]表示到i号的可能路线数
        vector<long long> dp(55);
        dp[a] = 1;

        dp[a + 1] = 1;
        for (int i = a + 2; i <= b; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        cout << dp[b] << endl;
    }

    return 0;
}

dp[i][j][k] 表示涂到第i个，当前颜色为j，初始颜色为k的方案数

dp[i][j][k] = dp[i - 1][(j + 1) % 3][k] + dp[i - 1][(j + 2) % 3][k];

因为 n = 1 时 不满足环形图，故需要特判

#include <iostream>

#include <vector>

#include <cstring>
using namespace std;

// dp[i][j][k] 表示涂到第i个，当前颜色为j，初始颜色为k的方案数

long long dp[55][55][55];
int main()
{
    int n;

    while (cin >> n)
    {

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

        for (int j = 0; j < 3; j++)
        {

            dp[1][j][j] = 1;
        }
        for (int i = 2; i <= n; i++)
        {

            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 3; k++)
                {
                    dp[i][j][k] = dp[i - 1][(j + 1) % 3][k] + dp[i - 1][(j + 2) % 3][k];
                }
            }

        }
        long long ans = 0;
        if (n > 1)

        {
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (i != j)
                    {
                        ans += dp[n][i][j];
                    }
                }
            }
        }

        else
        {
            ans = 3;
        }



        cout << ans << endl;
    }
    return 0;
}

Coding day 12

算法

编程语言

贪心算法解决节目安排问题，优先选择持续时间短且开始早的节目。动态规划解决楼梯走法问题，状态转移方程为dp[i]=dp[i-1]+dp[i-2]。斐波那契数列问题需注意数据范围。环形图染色问题采用动态规划或公式法求解，n≥2时适用公式(k-1)^n+(-1)^n*(k-1)。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Coding day 12

Coding day 12

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐