首页 > 代码库 > scauoj 17233 歌唱比赛
scauoj 17233 歌唱比赛
17233 歌唱比赛
时间限制:1000MS 内存限制:65535K
提交次数:8 通过次数:6 收入:37题型: 编程题 语言: G++;GCC
Description
Alice很喜欢唱歌。他准备参加一个歌唱比赛。Alice会唱N首歌曲，每一首歌都有演唱时间和音调。假设第i首歌的演唱时间为dura[i]，音调为tone[i]。Alice发现很难连续演唱不同音调的歌曲。当他唱完第i首歌之后准备唱第j首歌，他需要| tone[i]-tone[j] | 的时间去调整。已知Alice只有时间T去表演。假设一开始Alice就能马上进入状态演唱任意一首歌，并且他每一次选歌都是任意的。现在Alice想知道在给定的时限内他最多能够演唱多少首歌曲。
输入格式
多样例，EOF结束。对于每个样例，第一行为N。（1<=N<=15）第二行有N个整数dura[i]，表示每首歌的演唱时间。(dura[i]<=1000000)第三行有N个整数tone[i]，表示每首歌的音调。(tone[i]<=1000000)第四行一个整数T，表示Alice的表演时间。
输出格式
每个样例输出一个整数，表示Alice在给定的时限内他最多能够演唱多少首歌曲。
输入样例
59 5 2 5 58 7 1 3 314
输出样例
3
来源
Farmer
作者
201131000903
因为音调转化是费时间的，所以需要排个序，然后直接dfs就好了
#include <iostream>#include <stdio.h>#include <cstdlib>#include <algorithm>#include <cmath>#include <cstring>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <queue>#define cl(A) memset(A, 0, sizeof(A))using namespace std;typedef long long LL;const int maxn = 1e5+5;const int M = maxn*100;const int mod = 1e9+7;const double eps = 1e-7;const int inf = 0x3f3f3f;const LL INF = 1LL<<60;const int N = 1e5 + 7;int n;LL T;int ans;struct node { int dura; int tone; bool operator < (const node&a)const { if(tone!=a.tone) { return tone<a.tone; } else return dura<a.dura; }} si[20];void init() { ans=0; for(int i = 0; i < n; i++) { scanf("%d",&si[i].dura); } for(int i = 0; i < n; i++) { scanf("%d",&si[i].tone); } cin>>T; sort(si,si+n);// for(int i = 0; i < n; i++) {// cout<<si[i].dura<<" "<<si[i].tone<<endl;// }}void dfs(int cur,int remain,int cnt,int last) { ans=max(cnt,ans); if(cur==n)return; int waste=(last!=-1?abs(si[last].tone-si[cur].tone):0)+si[cur].dura; if(remain>=waste)dfs(cur+1,remain-waste,cnt+1,cur); dfs(cur+1,remain,cnt,last);}void solve() { dfs(0,T,0,-1); printf("%d\n",ans);}int main() {#ifdef local freopen("in", "r", stdin);#endif // local while(cin>>n) { init(); solve(); }}
scauoj 17233 歌唱比赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。