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在给定的时限内他最多能够演唱多少首歌曲。
输入样例
5 9 5 2 5 5 8 7 1 3 3 14
输出样例
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(); } }
原文：http://www.cnblogs.com/scau-zk/p/5856094.html
