题解 | #毕业bg#

毕业bg

http://www.nowcoder.com/practice/a3a99a0658a44cb1a37ddf5c164e21a6

dfs永远滴神

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 1000
int N, M;
struct act{
	int l;//持续时间
	int h;//快乐度
	int t;//离校时间
};
vector<act>v;
int dp[MAX][2];//dp[i][0]表示i时刻的已获取最大快乐度,dp[i][1]表示对应的获取活动的截止时间
int max_h, now_h;//最大/当前快乐度
int nowtime;//当前时间
vector<bool>visited;
int now_act_num;
bool cmp(act a1, act a2) {
	return a1.t < a2.l;
}
//已经参加完k活动,开始寻找下一个活动
void dfs(int k){
	if (now_h > dp[nowtime][0] && v[k].t <= dp[nowtime][1]) {
		dp[nowtime][0] = now_h; dp[nowtime][1] = v[k].t;
	}
	if (now_h <= dp[nowtime][0] && v[k].t > dp[nowtime][1]) {
		return;
	}
	//cout << "调用dfs,k=" << k << endl;
	//先判断是否存在下一个可以参加的活动
	int j = 0;
	for (; j< v.size(); j++) {
		if (!visited[j]&&nowtime + v[j].l <= v[j].t)break;
	}
	if (j == v.size()) {//没有可以参加的活动
		max_h = max(max_h, now_h);
		return;
	}

	//至少还有一个可以参加的活动
	for (int i = j; i < v.size(); i++) {
		if (!visited[i] && nowtime + v[i].l <= v[i].t) {
			now_h += v[i].h; nowtime += v[i].l;
			visited[i] = true; now_act_num--;
			dfs(i);
			visited[i] = false; now_act_num++;
			now_h -= v[i].h; nowtime -= v[i].l;
		}
	}
}
int main() {
	while (cin >> N) {
		if (N < 0)break;
		now_act_num = N;
		for (int i = 0; i < MAX; i++) {
			dp[i][0] = -1;
			dp[i][1] = 1 << 30;
		}
			
		for (int i = 0; i < N; i++) {
			act t;
			cin >> t.h >> t.l >> t.t;
			v.push_back(t);
			visited.push_back(false);
		}
		sort(v.begin(), v.end(), cmp);
		max_h = 0; now_h = 0; nowtime = 0;
		for (int i = 0; i < v.size(); i++) {
			now_h += v[i].h; nowtime += v[i].l;
			visited[i] = true; now_act_num--;
			dfs(i);
			visited[i] = false; now_act_num++;
			now_h -= v[i].h; nowtime -= v[i].l;
		}
		cout << max_h << endl;

	}
	return 0;
}
全部评论

相关推荐

1.自我介绍2.介绍一下mcp,&nbsp;skills3.了解react哪些状态管理库4.对话是sse还是什么?是用fetch还是EventSource?5.ts中的any&nbsp;和&nbsp;unknown讲一讲6.是直接用组件库的组件还是自己封装了一些别的7.代码输出题1function&nbsp;main()&nbsp;{{var&nbsp;a&nbsp;=&nbsp;1let&nbsp;b&nbsp;=&nbsp;2}console.log(a);console.log(b);}main()console.log(a);8.什么是块级作用域&nbsp;全局作用域&nbsp;函数作用域9.代码输出题2for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(i);},&nbsp;100);}10.代码输出题3for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&amp;lt;&nbsp;5;&nbsp;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}11.代码输出题4for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{var&nbsp;temp&nbsp;=&nbsp;isetTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}12.代码输出题5for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{var&nbsp;temp&nbsp;=&nbsp;iconsole.log(temp);},&nbsp;100);}printText(i)}13.点击控制台输出题export&nbsp;default&nbsp;function&nbsp;App()&nbsp;{const&nbsp;[count,&nbsp;setCount]&nbsp;=&nbsp;useState(0)console.log('render',count)return&nbsp;(&lt;div&gt;&lt;h1&gt;{count}&lt;/h1&gt;{setCount(count&nbsp;+&nbsp;1)setTimeout(()&nbsp;=&amp;gt;&nbsp;console.log('setTimeout',&nbsp;count),&nbsp;1000)}}&amp;gt;+1&lt;/div&gt;)}//这个组件点击按钮后,控制台的输出顺序和值如下://&nbsp;1.&nbsp;render&nbsp;1&nbsp;(组件重新渲染,&nbsp;count&nbsp;更新为&nbsp;1)//&nbsp;2.&nbsp;setTimeout&nbsp;0&nbsp;(1秒后输出,注意这里是&nbsp;0&nbsp;而不是&nbsp;1)14.算法:给有序数组arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5],返回平方后的排序//&nbsp;有序数组平方后排序const&nbsp;arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5]function&nbsp;solution(arr)&nbsp;{const&nbsp;len&nbsp;=&nbsp;arr.lengthconst&nbsp;result&nbsp;=&nbsp;new&nbsp;Array(len)let&nbsp;left&nbsp;=&nbsp;0let&nbsp;right&nbsp;=&nbsp;len&nbsp;-&nbsp;1let&nbsp;index&nbsp;=&nbsp;len&nbsp;-&nbsp;1while&nbsp;(left&nbsp;&amp;lt;=&nbsp;right)&nbsp;{if&nbsp;(arr[left]&nbsp;*&nbsp;arr[left]&nbsp;&amp;gt;&nbsp;arr[right]&nbsp;*&nbsp;arr[right])&nbsp;{result[index]&nbsp;=&nbsp;arr[left]&nbsp;*&nbsp;arr[left]left++}&nbsp;else&nbsp;{result[index]&nbsp;=&nbsp;arr[right]&nbsp;*&nbsp;arr[right]right--}index--}return&nbsp;result}console.log(solution(arr));15.反问
查看14道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务