ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客竞赛]209809.乐团派对(线性DP)

2022年8月23日 108点热度 0人点赞 0条评论

题目传送门:乐团派对 (nowcoder.com)

思路 / Thought

首先对能力值数组进行排序,因为选人的时候顺序没要求,升序的话方便考虑,如果i可以组成乐队的话,比i小的肯定可以组成。

定义dp[i]表示到i为止可以组成的最大合法乐团数量。

接下来就可以写状态转移方程

第i个人,要么分到前面的乐队,要么分到后面的乐队。

但是第N个只能分到前面的乐队,所以输出的答案应该是dp[N - a[N]] + 1。

如果a[N] > N就输出-1。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;

int a[maxn], dp[maxn];//dp[i] means from 1 to i, the count of teams

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1, a + 1 + N);//升序 
	
	for(int i = 1;i <= N; ++ i)
    {
        dp[i] = dp[i - 1];
        if(a[i] <= i)dp[i] = max(dp[i - a[i]] + 1, dp[i - 1]);
    }
    if(a[N] <= N)cout << dp[N - a[N]] + 1 << '\n';
    else cout << -1 << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP 动态规划 思维 牛客网 算法竞赛 线性dp
最后更新:2022年8月23日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号