NC15724. 小Q的口袋校园
描述
输入描述
第一行输入一个整数T（表示样例个数）
接下来T组样例
每组样例第一行输入一个整数N（表示有几项活动）
接下来N行，每行输入s,e,h,p 4个整数，分别代表一个活动的开始时间、结束时间、Happy值以及绩点数
0<=s<e<=24,1<=h,p<=100，1<=T,N<=20
输出描述
输出T行
一行输出一个样例对应的结果
小Q在一天内所能获得的最大 Happy值 与 绩点数
示例1
输入:
1 4 1 3 1 1 2 5 2 1 3 7 2 1 5 8 1 2
输出:
3 3
说明:
有两种方案C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 328K, 提交时间: 2018-06-07 09:57:03
#include<iostream>
#include<cstring>
using namespace std;
int n,a[30][2],v[30][2],visit[30],cnth,cntp;
void dfs(int now,int h,int p)
{
if(h>cnth)
{
cnth=h;
cntp=p;
}
else if(h==cnth)
{
if(p>cntp)
{
cnth=h;
cntp=p;
}
}
for(int i=0;i<n;i++)
{
if(!visit[i]&&a[i][0]>=now&&a[i][1]<=24)
{
visit[i]=true;
dfs(a[i][1],h+v[i][0],p+v[i][1]);
visit[i]=false;
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(visit,false,sizeof(visit));
cin>>n;
for(int i=0;i<n;i++)cin>>a[i][0]>>a[i][1]>>v[i][0]>>v[i][1];
cnth=-1;
cntp=-1;
dfs(0,0,0);
cout<<cnth<<" "<<cntp<<endl;
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2023-03-23 12:14:15
#include<bits/stdc++.h>
using namespace std;
struct node
{
int l,r,v,y;
}a[30];
int n,t,ans1,ans2;
void dfs(int t,int v,int y)
{
if(v>ans1||(v==ans1&&y>ans2))ans1=v,ans2=y;
for(int i=0;i<n;i++)if(a[i].l>=t)dfs(a[i].r,v+a[i].v,y+a[i].y);
}
int main()
{
scanf("%d",&t);
while(t--)
{
ans1=ans2=0;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].v,&a[i].y);
dfs(0,0,0);
cout<<ans1<<" "<<ans2<<endl;
}
return 0;
}