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

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>
            久久精品国产99国产精品澳门| 日韩亚洲精品电影| 欧美亚洲一区二区三区| 国产伦精品一区二区三区免费| 亚洲一区二区三区777| 一区二区三区久久| 国产精品一区在线观看你懂的| 欧美在线关看| 久久国产高清| 亚洲人成7777| 一区二区三区四区精品| 国产深夜精品| 欧美成人官网二区| 欧美日韩另类丝袜其他| 午夜久久tv| 久久婷婷国产麻豆91天堂| 亚洲精品韩国| 亚洲小说欧美另类社区| 激情综合网激情| 亚洲精品免费电影| 国产精品亚洲人在线观看| 欧美成人在线免费视频| 国产精品yjizz| 免费日本视频一区| 国产精品hd| 你懂的一区二区| 国产精品久久久一区麻豆最新章节 | 亚洲人午夜精品| 中文久久精品| 亚洲欧洲日夜超级视频| 亚洲天堂网在线观看| 亚洲国产成人午夜在线一区 | 久久精品官网| 欧美精品一区二区视频| 欧美主播一区二区三区| 欧美理论电影在线观看| 免费久久久一本精品久久区| 国产精品免费网站在线观看| 亚洲国产欧美在线| 影音先锋亚洲一区| 小处雏高清一区二区三区| 一区二区欧美激情| 久久综合亚洲社区| 久久久www成人免费无遮挡大片| 欧美日韩国产一级片| 欧美gay视频| 韩国久久久久| 性xx色xx综合久久久xx| 亚洲专区一区| 欧美日韩国产影片| 麻豆精品网站| 国产精品美女久久久浪潮软件| 欧美成人一区二区三区在线观看| 久久国产欧美精品| 久久精品视频va| 欧美日韩另类丝袜其他| 欧美高清视频一区二区| 国产亚洲午夜高清国产拍精品| 亚洲欧洲精品一区二区三区| 精品二区视频| 亚洲欧美日韩成人高清在线一区| 亚洲国产另类 国产精品国产免费| 亚洲无线视频| 亚洲午夜一区二区三区| 欧美精品亚洲| 欧美国产免费| 日韩亚洲欧美综合| 欧美多人爱爱视频网站| 美女精品国产| 国产在线视频欧美一区二区三区| 亚洲一区二区三区国产| 亚洲一区二区欧美日韩| 欧美久久电影| 亚洲人成人77777线观看| 亚洲国产女人aaa毛片在线| 久久精品卡一| 午夜精品免费视频| 韩日欧美一区二区| 久久精品国产第一区二区三区最新章节 | 日韩一级免费| 夜夜狂射影院欧美极品| 欧美国产精品日韩| 亚洲国产精品激情在线观看| 亚洲精品国产精品国自产在线| 老司机免费视频一区二区| 美女精品在线| 亚洲精品久久久蜜桃| 美日韩免费视频| 久久人人爽爽爽人久久久| 精品成人免费| 欧美www视频| 99这里有精品| 午夜在线视频观看日韩17c| 国产精品久久一卡二卡| 亚洲一级特黄| 另类激情亚洲| 亚洲精品国产精品国产自| 欧美精品国产精品| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 久久久国产精彩视频美女艺术照福利| 国产日韩av高清| 久久久噜噜噜久久狠狠50岁| 欧美高清视频在线 | 欧美视频1区| 亚洲欧美激情视频| 欧美sm重口味系列视频在线观看| 亚洲欧洲日本国产| 欧美日韩在线播| 午夜久久久久久| 欧美成人精品一区| 亚洲国产高清视频| 国产精品嫩草久久久久| 久久精品91| avtt综合网| 久久久久这里只有精品| 一本综合精品| 韩国av一区| 欧美日韩三级在线| 久久国产精品毛片| 一本色道久久| 欧美高清在线观看| 中文精品视频一区二区在线观看| 在线观看成人一级片| 欧美日韩三区四区| 开元免费观看欧美电视剧网站| 一区二区三区精品视频| 免费看成人av| 久久黄色级2电影| 亚洲天堂成人在线观看| 影音先锋亚洲视频| 国产日本欧美一区二区三区在线| 欧美激情国产日韩精品一区18| 99精品欧美一区二区三区| 久久久人成影片一区二区三区 | 欧美日韩91| 久热re这里精品视频在线6| 午夜精品福利电影| 欧美激情影院| 欧美中文字幕第一页| 亚洲一卡久久| 亚洲日本理论电影| 亚洲美女毛片| 91久久嫩草影院一区二区| 日韩视频在线你懂得| 久久精品五月婷婷| 欧美一区二区三区在线免费观看 | 黄色国产精品一区二区三区| 国产精品入口福利| 欧美午夜美女看片| 欧美日韩国产成人精品| 久久aⅴ国产欧美74aaa| 亚洲欧美国产另类| 亚洲午夜国产成人av电影男同| 亚洲精品视频在线播放| 亚洲高清影视| 欧美激情一区二区在线| 欧美激情视频一区二区三区不卡| 久久综合九色欧美综合狠狠| 久久漫画官网| 久久午夜国产精品| 美女久久网站| 另类av导航| 欧美激情精品久久久久久大尺度| 欧美成人国产| 亚洲黄色小视频| 日韩午夜在线观看视频| 亚洲最新色图| 亚洲欧美中文字幕| 欧美一区二区三区日韩| 久久国产99| 欧美激情aaaa| 欧美涩涩网站| 国产美女扒开尿口久久久| 国产一区二区丝袜高跟鞋图片 | 欧美h视频在线| 欧美紧缚bdsm在线视频| 国产精品v日韩精品| 国产日韩欧美| 亚洲国产日韩欧美综合久久| 亚洲二区视频| 亚洲视频免费观看| 久久国产精彩视频| 欧美aaa级| 亚洲国产日韩欧美在线动漫| 欧美激情成人在线| 99re热精品| 欧美在线精品免播放器视频| 久久久久综合一区二区三区| 欧美激情视频给我| 国产精品视频在线观看| 在线日韩成人| 亚洲午夜国产一区99re久久| 久久久噜噜噜久久久| 美女诱惑黄网站一区| 亚洲精品小视频| 欧美一区二区性| 欧美日本中文字幕| 国产乱码精品一区二区三区五月婷| 亚洲人成在线播放| 欧美在线|欧美|