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

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>
            亚洲女同同性videoxma| 一区二区久久久久久| 亚洲一卡久久| 夜夜嗨一区二区三区| 欧美性视频网站| 性做久久久久久免费观看欧美 | 欧美护士18xxxxhd| 日韩网站在线观看| 日韩视频一区二区三区在线播放免费观看 | 久久精品91| 亚洲日韩第九十九页| 亚洲伦理自拍| 国产麻豆视频精品| 嫩模写真一区二区三区三州| 免费成人网www| 亚洲欧美日韩视频二区| 欧美制服第一页| 亚洲黄色在线| 亚洲午夜激情网页| 国内精品久久久久影院优| 欧美黄在线观看| 国产精品户外野外| 老色鬼久久亚洲一区二区| 欧美日韩福利视频| 久久久久成人精品免费播放动漫| 另类国产ts人妖高潮视频| 一本不卡影院| 久久精品国产综合精品| 亚洲一二三四区| 蜜臀va亚洲va欧美va天堂| 翔田千里一区二区| 欧美人成免费网站| 久久精品国产第一区二区三区最新章节| 男女视频一区二区| 欧美一级视频| 欧美欧美天天天天操| 欧美在线你懂的| 欧美特黄一区| 欧美a级在线| 国产欧美日韩高清| 99成人精品| 亚洲国产一区二区三区a毛片| 亚洲自拍三区| 亚洲视频一区二区在线观看| 久久一区二区三区四区| 亚洲欧美视频一区二区三区| 欧美精品一区二区三区视频| 久久久久久久波多野高潮日日| 欧美日韩综合在线| 亚洲国产精品高清久久久| 国产欧美综合在线| 在线亚洲国产精品网站| 亚洲精品欧美日韩专区| 看片网站欧美日韩| 欧美成人精品在线| 亚洲激情专区| 欧美www视频| 亚洲欧洲日本专区| 亚洲精品国久久99热| 美女精品在线观看| 欧美国产日产韩国视频| 亚洲第一伊人| 另类欧美日韩国产在线| 亚洲福利在线看| 亚洲美女av网站| 欧美日韩国产在线| 一本色道久久综合亚洲精品不| 一区二区欧美日韩| 欧美区视频在线观看| 亚洲精品日日夜夜| 亚洲一区制服诱惑| 国产精品美女xx| 午夜精品久久久久久久99黑人| 欧美一区久久| 国内精品久久久久影院薰衣草| 久久久999成人| 欧美福利视频一区| 日韩一级片网址| 国产精品爱久久久久久久| 亚洲综合视频网| 久久中文在线| 亚洲黄色三级| 国产精品久久久久久模特| 午夜亚洲性色视频| 免费看黄裸体一级大秀欧美| 亚洲精品美女在线| 欧美午夜片欧美片在线观看| 午夜久久久久久久久久一区二区| 久久免费国产| 一本色道精品久久一区二区三区| 欧美性理论片在线观看片免费| 亚洲欧美成人综合| 欧美xxx在线观看| 亚洲欧美日韩国产一区| 韩国v欧美v日本v亚洲v| 欧美精品一区二区视频| 欧美一区二区精品| 亚洲欧洲精品一区| 久久九九精品| 亚洲午夜久久久久久久久电影网| 国产日韩欧美在线播放不卡| 免费成人在线观看视频| 亚洲欧美日韩在线一区| 亚洲电影免费观看高清| 香蕉久久久久久久av网站| 亚洲激情影院| 国产一区二区三区免费观看| 欧美久久久久久| 久久视频免费观看| 亚洲香蕉成视频在线观看| 欧美大片一区二区三区| 性做久久久久久免费观看欧美| 亚洲乱码国产乱码精品精天堂 | 午夜欧美精品| 最新中文字幕亚洲| 国产一区二区成人久久免费影院| 欧美剧在线观看| 久久亚洲风情| 久久九九精品99国产精品| 一区二区三区日韩在线观看| 亚洲福利免费| 欧美激情二区三区| 久久夜色精品国产| 久久国产夜色精品鲁鲁99| 一区二区三区黄色| 亚洲毛片在线免费观看| 91久久线看在观草草青青| 国产一区二区黄| 国产无遮挡一区二区三区毛片日本| 欧美日韩精品一区二区在线播放 | 亚洲午夜在线视频| a4yy欧美一区二区三区| 亚洲高清视频在线| 欧美激情综合| 欧美成年人网站| 免费在线观看一区二区| 久久久久久网址| 久久免费视频在线观看| 久久久综合免费视频| 久久久777| 久久久久免费| 蜜桃av综合| 亚洲电影成人| 亚洲欧洲一区二区天堂久久| 亚洲欧洲视频| 一区二区三区视频观看| avtt综合网| 亚洲一区二区三区四区五区午夜 | 午夜亚洲福利| 久久精品国产2020观看福利| 久久成人国产| 美日韩免费视频| 欧美日韩国产精品专区| 国产精品av免费在线观看| 国产老女人精品毛片久久| 国产亚洲精品aa| 亚洲福利视频一区| 日韩天堂在线观看| 亚洲欧美日韩国产成人| 欧美专区在线播放| 欧美激情一区二区三区| 亚洲精品一区二区网址| 亚洲一级电影| 久久久亚洲精品一区二区三区| 欧美成人午夜激情视频| 国产精品成人播放| 韩日视频一区| 99re热这里只有精品免费视频| 亚洲伊人网站| 麻豆91精品| 99精品国产在热久久婷婷| 先锋影院在线亚洲| 欧美顶级艳妇交换群宴| 国产伦精品一区二区三| 亚洲国产日日夜夜| 亚洲欧美日韩精品久久亚洲区| 狂野欧美激情性xxxx| 一区二区三欧美| 久久综合给合久久狠狠色| 欧美日韩性视频在线| 国内久久精品| 亚洲一级电影| 亚洲国产精品第一区二区三区 | 一区二区三区鲁丝不卡| 玖玖视频精品| 国产亚洲激情| 亚洲欧美另类国产| 亚洲电影免费观看高清| 性欧美办公室18xxxxhd| 欧美日韩999| 在线欧美电影| 久久久免费精品视频| 一区二区欧美日韩| 欧美精品1区2区| 亚洲成色最大综合在线| 欧美淫片网站| 亚洲性图久久| 欧美日韩无遮挡| 亚洲精品网站在线播放gif| 久久精品一区|