赞
踩
已知N个时间的发生时刻和结束时刻(见下表)。一些在时间上没有重叠的事件,可以构成一个事件序列,如事件{ 2,8,10 }。
事件序列包含的事件数目,称为该事件序列的长度。请编程找出一个最长事件序列
up主这里为了让输入方便一点 就用文件的方式 读取数据
文件名:1.txt
- 0 1 3
- 1 3 4
- 2 0 7
- 3 3 8
- 4 2 9
- 5 5 10
- 6 6 12
- 7 4 14
- 8 10 15
- 9 8 18
- 10 15 19
- 11 15 20
- #include<iostream>
- #include<fstream>
- using namespace std;
- struct b
- {
- int number;
- int head;
- int end;
- };
- b tp[12];
- int a[12]={0};
-
- int maxs[12]={0};
- int max_len=0;
- int max_bs=0;
-
-
- int getEnd(int n) //获取 n=number 的end 的值
- {
- int i,end;
- for(i=0;i<=11;i++)
- {
- if(tp[i].number==n)
- {
- end=tp[i].end;
- break;
- }
- }
- return end;
- }
- int getHead(int n) //获取 n=number 的 head 的值
- {
- int i,head;
- for(i=0;i<=11;i++)
- {
- if(tp[i].number==n)
- {
- head=tp[i].head;
- break;
- }
- }
- return head;
- }
-
- bool End(int n) //当前深度是否还能继续
- {
- int i,j;
-
- if(n>0)
- {
- for(i=0;i<n;i++)
- if(a[i]==a[n]) return true; //一旦有重复的
-
- if(getHead(a[n])>=getEnd(a[n-1])) return false;
- }
-
- else
- {
- return false;
- }
-
- return true;
- }
- void bre(int n)
- {
- static int max=0;
- int i=0,sum=0;
- for(i=0;i<n;i++)
- {
- sum=sum+getEnd(a[i])-getHead(a[i]);
- }
- if(sum>max)
- {
- max=sum;
- max_bs=sum;
- max_len=n;
- for(i=0;i<n;i++)
- maxs[i]=a[i];
- }
- }
-
- void getAll(int n,int num)
- {
- //当前的end 已经没有所匹配的head的时候
- int i;
- a[n]=num;
- if(End(n))
- bre(n);
- else
- {
- for(i=0;i<=11;i++)
- getAll(n+1,i);
- }
- }
-
- int main()
- {
- int number,head,end,i;
- ifstream out("1.txt");
- if (!out.is_open())
- {
- cout << "Error opening file"; exit (1);
- }
- i=0;
- while (!out.eof())
- {
- out>>number>>head>>end;
- tp[i].number=number;
- tp[i].head=head;
- tp[i].end=end;
- i++;
- }
-
- for(i=0;i<12;i++)
- getAll(0,i);
-
- for(i=0;i<max_len;i++)
- cout<<maxs[i]<<" ";
- cout<<endl<<"最长的事件长度为:"<<max_bs;
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。