青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 195,  comments - 30,  trackbacks - 0

A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.


Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.

 

Input

A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.

Output

For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.

Sample Input

4  50 2  10 1   20 2   30 1
7  20 1   2 1   10 3  100 2   8 2
5 20  50 10

 

Sample Output

80
185

 

Hint

The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.


#include<iostream>
#include<cstdlib>
using namespace std;
#define MAX 10001
#define min(a,b) ((a)<(b) ? (a) : (b))
int father[MAX];
int p[MAX];
int result[MAX];
struct job{
     int value;
     int T;
  }JOB[MAX];
bool operator <(job job1,job job2)
 {
  if(job1.value>job2.value)
  return true;
  else
  return false;
 } 
 int find(int x)  //·µ»ØµÚ£Ø½ÚµãËùÊô¼¯ºÏµÄ¸ù½áµã
  {
int px=x;
while(p[px]>=0)
   px=p[px];
int tmp;
while(p[x]>=0)//ӦΪ³õֵΪ¸º
{
   tmp=p[x];
   p[x]=px;
   x=tmp;
}
return px;
}

   void UNION(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
   return ;
int tmp=p[x]+p[y];
if(p[x]>p[y])
{
   p[y]=tmp;
   p[x]=y;
}
else
{
   p[x]=tmp;
   p[y]=x;
}
}
 
  int main()
  {
  freopen("s.txt","r",stdin);
  freopen("key.txt","w",stdout);
  int num,temp=0;
  while(cin>>num)
  {
  memset(result,0,num);
  int i,l,j,k=0;
  for( i=0;i<num;i++)
  {
   cin>>JOB[i].value>>JOB[i].T;
   father[i]=i;
   p[i]=-1;
  }
  sort(JOB,JOB+num);
  for(i=0;i<num;i++)
  {
   j=find(min(JOB[i].T,num-1));//
   if(father[j]!=0)
       {
     k++;
     result[k]=i;
        l=find(father[j]-1);
        UNION(l,j);
        father[j]=father[l];
    }
  }
  i=0;
  for(j=1;j<=k;j++)
  { 
   i+=JOB[result[j]].value;}
    cout<<i<<endl;
   }

  //system("PAUSE");
  return   0;
  }
對著課本寫得,自己都看不怎么懂。

posted on 2009-07-02 13:11 luis 閱讀(525) 評論(0)  編輯 收藏 引用 所屬分類: 貪心*二分
<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

文章分類

文章檔案

友情鏈接

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品毛片一区二区三区 | 亚洲线精品一区二区三区八戒| 欧美三级乱码| 夜夜爽av福利精品导航| 亚洲午夜羞羞片| 亚洲人成毛片在线播放| 欧美激情乱人伦| 欧美一区二区三区在线| 伊人久久久大香线蕉综合直播 | 免费视频久久| 一本综合精品| 免费不卡在线观看| 久久精品日韩欧美| 国产九区一区在线| 91久久精品美女高潮| 国产精品一区亚洲| 亚洲最新在线视频| 美乳少妇欧美精品| 亚洲欧美日本日韩| 亚洲精品视频免费观看| 一区二区三区无毛| 国产午夜精品在线| 国产午夜精品一区理论片飘花| 欧美成人午夜剧场免费观看| 午夜精品一区二区三区在线视| 欧美成人综合在线| 欧美国产精品日韩| 国产精品萝li| 久久xxxx| 亚洲韩国精品一区| 国产精品国产三级国产普通话99| 国产精品乱看| 欧美96在线丨欧| 国产精品欧美日韩一区二区| 麻豆av一区二区三区| 国产精品国产成人国产三级| 欧美成人有码| 久久精品九九| 欧美三级精品| 亚洲春色另类小说| 国产一区二区三区高清| 欧美激情性爽国产精品17p| 国产伦精品一区二区三区免费 | 欧美一级片在线播放| 在线不卡亚洲| 国产欧美精品xxxx另类| 亚洲主播在线播放| 99国产精品久久久久久久久久| 美女视频网站黄色亚洲| 国产精品蜜臀在线观看| 亚洲人午夜精品| 伊人久久亚洲影院| 午夜在线播放视频欧美| 亚洲免费在线视频一区 二区| 一本色道久久综合亚洲精品不| 欧美精品在线观看91| 麻豆成人在线播放| 狠狠色噜噜狠狠色综合久| 亚洲小少妇裸体bbw| 亚洲自拍偷拍福利| 国产精品久久久久久久久久三级| 欧美一区1区三区3区公司| 欧美日韩激情小视频| 亚洲国产老妈| 亚洲精品少妇30p| 一本色道久久综合狠狠躁篇怎么玩| 欧美激情第六页| 国产日韩欧美一区二区三区在线观看| 亚洲精品国产精品国自产观看浪潮| 久久综合国产精品台湾中文娱乐网| 欧美在线不卡| 欧美在线观看你懂的| 国产精品嫩草99av在线| 亚洲免费在线观看| 久久久久久久尹人综合网亚洲| 久久免费一区| 亚洲二区免费| a4yy欧美一区二区三区| 欧美三级第一页| 亚洲性图久久| 久久久久免费观看| 亚洲高清精品中出| 欧美大片在线看| 在线视频你懂得一区| 欧美一区二区三区久久精品| 国语精品中文字幕| 麻豆精品在线播放| 99视频超级精品| 欧美一区午夜视频在线观看| 一区二区三区在线免费播放| 欧美不卡在线视频| 亚洲图片欧美一区| 久久深夜福利免费观看| 亚洲美女视频在线观看| 欧美性一二三区| 久久激情久久| 亚洲美女毛片| 久久在线视频在线| 一本久道综合久久精品| 国产女主播一区二区| 欧美成人一区二区| 午夜国产精品视频| 亚洲国产高清视频| 久久er99精品| 99精品欧美一区| 国产婷婷97碰碰久久人人蜜臀| 亚洲精品乱码久久久久久日本蜜臀| 国产一区导航| 欧美伦理在线观看| 久久人人97超碰精品888 | 欧美xart系列高清| 亚洲免费在线观看视频| 亚洲国产毛片完整版| 欧美亚洲在线| 日韩视频中文字幕| 在线成人国产| 国产日韩一级二级三级| 欧美视频二区| 欧美激情麻豆| 久久嫩草精品久久久久| 亚洲嫩草精品久久| 一本一本大道香蕉久在线精品| 亚洲美女精品久久| 一区二区视频欧美| 国产女精品视频网站免费 | 久久激情综合网| 亚洲一区二区精品在线| 狠狠色狠狠色综合日日tαg| 国产精品美女久久久免费| 欧美精品一区二区三区久久久竹菊 | 久久综合九九| 久久精品一区二区三区四区 | 久久香蕉国产线看观看av| 亚洲网址在线| 亚洲天堂网在线观看| 亚洲三级国产| 亚洲精品国产系列| 亚洲美女免费视频| 亚洲精品久久久久久一区二区| 欧美日韩国产一区二区三区| 裸体女人亚洲精品一区| 久久se精品一区二区| 亚洲女人天堂成人av在线| 亚洲资源av| 亚洲欧美国产高清| 欧美一区高清| 久久久国产91| 免费亚洲网站| 欧美极品aⅴ影院| 欧美日韩卡一卡二| 国产精品乱码一区二区三区| 国产精品视频网站| 国产主播一区二区三区| 激情综合色丁香一区二区| 影音先锋日韩精品| 亚洲国产视频直播| 99热免费精品在线观看| 亚洲一区二区三区欧美| 欧美在线电影| 欧美高清在线视频| 一本久久综合亚洲鲁鲁五月天| 玖玖玖国产精品| 欧美大片专区| 亚洲精品美女在线| 性欧美xxxx视频在线观看| 久久久久久久久蜜桃| 欧美高清在线视频| 国产精品网站在线观看| 在线精品亚洲| 一本一本久久a久久精品综合麻豆| 国产亚洲精品久久久久动| 在线精品一区| 亚洲一区二区毛片| 美女网站久久| 中日韩男男gay无套| 欧美一级一区| 欧美另类女人| 狠狠爱成人网| 亚洲视频 欧洲视频| 久久亚洲精品视频| 日韩视频在线一区| 久久久久久97三级| 国产精品va在线| 亚洲国产精品t66y| 欧美亚洲免费电影| 亚洲第一福利社区| 欧美一区二区网站| 欧美视频免费| 亚洲片区在线| 久久色在线播放| 亚洲在线观看| 欧美日韩国产色视频| 在线电影国产精品| 欧美一区久久| 一本到高清视频免费精品| 免费在线成人av| 韩国成人福利片在线播放| 午夜精品福利一区二区三区av| 亚洲欧美一区二区视频| 亚洲国产一区二区视频|