江西财经大学第一届程序设计竞赛 G题 小Q的口袋校园

链接：https://www.nowcoder.com/acm/contest/115/G
来源：牛客网

题目描述

输入描述:

第一行输入一个整数T（表示样例个数）
接下来T组样例
每组样例第一行输入一个整数N（表示有几项活动）
接下来N行，每行输入s,e,h,p 4个整数，分别代表一个活动的开始时间、结束时间、Happy值以及绩点数
0<=s 
输出描述:
 
输出T行
一行输出一个样例对应的结果
小Q在一天内所能获得的最大 Happy值 与 绩点数
  示例1    
输入
  
1
4
1 3 1 1
2 5 2 1
3 7 2 1
5 8 1 2
    
输出
  
3 3
    
说明
  
有两种方案
1）选择 第1、3两个活动，可以获得 Happy值 3 和 绩点数 2；
2）选择 第2、4两个活动，可以获得 Happy值 3 和 绩点数 3.
      
看了三生锁链的博客，链接：nowcoder contest#115 江西财经大学第一届程序设计竞赛 G 小Q的口袋校园 记忆化搜索 DP - CSDN博客  https://blog.csdn.net/a912952381/article/details/80032165 ，这位博主用的是dfs，发现数据不是很大，还真的是可以
 
就是先对数据进行排序，开始时间小的在前面，每件事都有两个选择，选（要满足第i件事的e值>=第i-1件事的e值）与不选，
 
再随时更新答案就可以了，看代码吧：
  
#include
#include
#include
using namespace std;
int n,m,k,t,ans1,ans2;
struct node{int s,e,h,p;
}str[25];
bool cmp(node s1,node s2)
{return s1.s<s2.s;
}
void dfs(int i,int a,int b,int time)//i表示第几件事，a，b分别表示happy值和绩点，time表示上一件事的e值 
{if(ans1b)){ans1=a;ans2=b;}if(i>=n)//终止条件 return ;if(str[i].s>=time)//要满足这件事的e值>=上一件事的e值 
    {dfs(i+1,a+str[i].h,b+str[i].p,str[i].e);}dfs(i+1,a,b,time);
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i)scanf("%d%d%d%d",&str[i].s,&str[i].e,&str[i].h,&str[i].p);ans1=ans2=0;sort(str,str+n,cmp);dfs(0,0,0,0);printf("%d %d\n",ans1,ans2);}return 0;} 
  
 刚刚本来想再找找有没有贪心的写法（我不太会贪心啊），又发现了一个动态规划（好像也可以叫贪心）的写法，和背包问题很像，果然打比赛的都是高手（至少在我眼里），我这个就不加注释了，应该看得懂，代码如下：
  
#include
#include
#include
using namespace std;
int n,m,k,t;
int ans1[30],ans2[30];
struct node{int s,e,h,p;
}str[30];
bool cmp(node s1,node s2)
{return s1.s<s2.s;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i)scanf("%d%d%d%d",&str[i].s,&str[i].e,&str[i].h,&str[i].p);sort(str,str+n,cmp);memset(ans1,0,sizeof(ans1));memset(ans2,0,sizeof(ans2));for(int i=0;i){for(int j=str[i].e;j<=24;j++){if(ans1[j]str[i].h){ans1[j]=ans1[str[i].s]+str[i].h;ans2[j]=ans2[str[i].s]+str[i].p;}else if(ans1[j]==ans1[str[i].s]+str[i].h){ans2[j]=max(ans2[j],ans2[str[i].s]+str[i].p);}}} printf("%d %d\n",ans1[24],ans2[24]);}return 0;} 
  
 
 
 
转载于:https://www.cnblogs.com/6262369sss/p/8908613.html
                        

                        

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！