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

POJ 1015 Jury Compromise 動態規劃

Description

In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.
Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
We will now make this more precise: given a pool of n potential jurors and two values di (the defence's value) and pi (the prosecution's value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,..., n} with m elements, then D(J ) = sum(dk) k belong to J
and P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.
For an optimal jury J , the value |D(J) - P(J)| must be minimal. If there are several jurys with minimal |D(J) - P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.
You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.

Input

The input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members.
These values will satisfy 1<=n<=200, 1<=m<=20 and of course m<=n. The following n lines contain the two integers pi and di for i = 1,...,n. A blank line separates each round from the next.
The file ends with a round that has n = m = 0.

Output

For each round output a line containing the number of the jury selection round ('Jury #1', 'Jury #2', etc.).
On the next line print the values D(J ) and P (J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.
Output an empty line after each test case.

Sample Input

4 2
1 2
2 3
4 1
6 2
0 0 

Sample Output

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3 

Hint

If your solution is based on an inefficient algorithm, it may not execute in the allotted time.

Source

 

    在遙遠的國家佛羅布尼亞,嫌犯是否有罪,須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選n 個人作為陪審團的候選人,然后再從這n 個人中選m 人組成陪審團。選m 人的辦法是:控方和辯方會根據對候選人的喜歡程度,給所有候選人打分,分值從0 到20。為了公平起見,法官選出陪審團的原則是:選出的m 個人,必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同,那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團方案。
    為敘述問題方便,現將任一選擇方案中,辯方總分和控方總分之差簡稱為“辯控差”,辯方總分和控方總分之和稱為“辯控和”。第i 個候選人的辯方總分和控方總分之差記為V(i),辯方總分和控方總分之和記為S(i)。現用f(j, k)表示,取j 個候選人,使其辯控差為k 的所有方案中,辯控和最大的那個方案(該方案稱為“方案f(j, k)”)的辯控和。并且,我們還規定,如果沒法選j 個人,使其辯控差為k,那么f(j, k)的值就為-1,也稱方案f(j, k)不可行。本題是要求選出m 個人,那么,如果對k 的所有可能的取值,求出了所有的f(m, k) (-20×m≤ k ≤ 20×m),那么陪審團方案自然就很容易找到了。
    問題的關鍵是建立遞推關系。需要從哪些已知條件出發,才能求出f(j, k)呢?顯然,方案f(j, k)是由某個可行的方案f(j-1, x)( -20×m ≤ x ≤ 20×m)演化而來的。可行方案f(j-1, x)能演化成方案f(j, k)的必要條件是:存在某個候選人i,i 在方案f(j-1, x)中沒有被選上,且x+V(i) = k。在所有滿足該必要條件的f(j-1, x)中,選出 f(j-1, x) + S(i) 的值最大的那個,那么方案f(j-1, x)再加上候選人i,就演變成了方案 f(j, k)。這中間需要將一個方案都選了哪些人都記錄下來。不妨將方案f(j, k)中最后選的那個候選人的編號,記在二維數組的元素path[j][k]中。那么方案f(j, k)的倒數第二個人選的編號,就是path[j-1][k-V[path[j][k]]。假定最后算出了解方案的辯控差是k,那么從path[m][k]出發,就能順藤摸瓜一步步求出所有被選中的候選人。初始條件,只能確定f(0, 0) = 0。由此出發,一步步自底向上遞推,就能求出所有的可行方案f(m, k)( -20×m ≤ k ≤ 20×m)。實際解題的時候,會用一個二維數組f 來存放f(j, k)的值。而且,由于題目中辯控差的值k 可以為負數,而程序中數租下標不能為負數,所以,在程序中不妨將辯控差的值都加上400,以免下標為負數導致出錯,即題目描述中,如果辯控差為0,則在程序中辯控差為400。

#include <iostream>
using namespace std;

int p[201],d[201],result[21];
int dp[21][801],path[21][801];

int cmp(const void *a,const void *b){
    
return *(int *)a-*(int *)b;
}

bool select(int a,int b,int i){
    
while(a>0 && path[a][b]!=i){
        b
-=p[path[a][b]]-d[path[a][b]];
        a
--;
    }

    
return (a!=0)?true:false;
}

int main(){
    
int i,j,k,a,b,n,m,origin,ca=1;
    
while(scanf("%d %d",&n,&m),n||m){
        
for(i=1;i<=n;i++)
            scanf(
"%d %d",p+i,d+i);
        memset(dp,
-1,sizeof(dp));
        memset(path,
0,sizeof(path));
        origin
=m*20;
        
for(dp[0][origin]=j=0;j<m;j++)
            
for(k=0;k<=origin*2;k++)
                
if(dp[j][k]>=0){
                    
for(i=1;i<=n;i++)
                        
if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i]){
                            a
=j,b=k;
                            
if(!select(a,b,i)){
                                dp[j
+1][k+p[i]-d[i]]=dp[j][k]+p[i]+d[i];
                                path[j
+1][k+p[i]-d[i]]=i;
                            }

                        }

                }

        
for(i=origin,j=0;dp[m][i+j]<0 && dp[m][i-j]<0;j++);
        k
=dp[m][i+j]>dp[m][i-j]?i+j:i-j;
        printf(
"Jury #%d\n",ca++);
        printf(
"Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][k]+k-origin)/2, (dp[m][k]-k+origin)/2);
        
for(i=1;i<=m;i++){
            result[i]
=path[m-i+1][k];
            k
-=p[result[i]]-d[result[i]];
        }

        qsort(result
+1,m,sizeof(int),cmp);
        
for(i=1;i<=m;i++)
            printf(
" %d",result[i]);
        printf(
"\n");
        printf(
"\n");
    }

    
return 0;
}


 

posted on 2009-06-23 17:08 極限定律 閱讀(4799) 評論(6)  編輯 收藏 引用 所屬分類: ACM/ICPC

評論

# re: POJ 1015 Jury Compromise 動態規劃 2009-09-09 14:03 boa

不知道為什么這種方法uva和tju上是wa啊?難道是這兩個網站不判special judge?  回復  更多評論   

# re: POJ 1015 Jury Compromise 動態規劃 2010-05-06 23:03 Cre_nws

麻煩問一下" if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i])"當k=0時,p[i]-d[i]如果為負值,那么會不會產生運行時錯誤啊?!謝啦!  回復  更多評論   

# re: POJ 1015 Jury Compromise 動態規劃 2010-08-05 22:33 cxb

@Cre_nws
k應該不會取到0,因為取到0就意味著“辯控差”為負的最大,即已經到了j=m-1次循環,并且所有的陪審員都是p:0 s:20,此時k=0,并且整個循環已經結束了,這就是板主為何要將origin=m*20的原因之所在。有不對的地方,請指正~  回復  更多評論   

# re: POJ 1015 Jury Compromise 動態規劃 2010-09-03 14:58 tel

效率不是很高啊  回復  更多評論   

# re: POJ 1015 Jury Compromise 動態規劃 2010-10-14 19:59 songtianyi

效率已經不錯了  回復  更多評論   

# re: POJ 1015 Jury Compromise 動態規劃 2011-08-05 20:33 asdf

這個算法有后效性吧。就是在i的選取上。  回復  更多評論   

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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爱| 亚洲二区视频在线| 国产一区二区三区四区hd| 午夜老司机精品| 亚洲欧美怡红院| 激情91久久| 亚洲第一视频网站| 国产精品扒开腿爽爽爽视频| 午夜在线成人av| 久久青草久久| 正在播放欧美视频| 午夜精品久久久久久久久久久久| 精品1区2区| 日韩一级黄色大片| 国产色综合天天综合网| 亚洲国产精品va在线看黑人| 国产精品久久久免费| 久久婷婷影院| 欧美揉bbbbb揉bbbbb| 久久九九精品| 欧美精品在线观看播放| 久久久精品视频成人| 欧美国产一区视频在线观看 | 巨乳诱惑日韩免费av| 99精品视频免费全部在线| 午夜伦理片一区| 夜夜嗨av色一区二区不卡| 欧美一站二站| 亚洲一区二区三区国产| 免费久久99精品国产自| 久久av红桃一区二区小说| 男女激情久久| 久久亚洲欧美| 国产欧美91| 在线视频欧美一区| 日韩一本二本av| 久久久久久婷| 欧美在线网站| 国产精品成人观看视频免费 | 久久精品电影| 午夜激情综合网| 欧美精品在欧美一区二区少妇| 久久综合给合久久狠狠色| 国产精品一区二区三区四区五区| 亚洲精品久久久久久一区二区 | 国产精品私房写真福利视频| 亚洲欧洲精品一区| 亚洲高清色综合| 久久婷婷国产麻豆91天堂| 久久亚洲国产精品日日av夜夜| 国产精品一区二区三区久久 | 亚洲高清成人| 在线视频国内自拍亚洲视频| 欧美中文字幕视频| 久久精品导航| 国产午夜精品理论片a级探花| 亚洲永久精品大片| 午夜日韩激情| 国产农村妇女精品一区二区| 亚洲一区二区动漫| 欧美一二区视频| 国产乱码精品一区二区三区av| 亚洲视频免费看| 欧美亚洲一区| 国产一区二区三区网站| 久久久久99| 欧美国产日韩在线观看| 日韩视频免费| 欧美午夜欧美| 香蕉精品999视频一区二区| 欧美一区高清| 在线观看一区欧美| 欧美成人精品在线观看| 亚洲免费观看高清在线观看| 亚洲一区二区不卡免费| 国产欧美丝祙| 久久久久网站| 99ri日韩精品视频| 国产欧美高清| 国产精品日韩欧美一区二区三区 | 在线观看国产成人av片| 免费av成人在线| 亚洲人成亚洲人成在线观看| 亚洲一区二区三区精品在线| 国产噜噜噜噜噜久久久久久久久| 久久黄色网页| 亚洲人成在线影院| 欧美亚洲综合久久| 亚洲欧洲一区二区在线播放| 国产精品久久一卡二卡| 久久乐国产精品| 99re6这里只有精品视频在线观看| 欧美一区二区免费视频| 亚洲国产精品毛片| 欧美视频免费看| 久久九九电影| 亚洲一区二区三区777| 欧美www视频| 午夜精品亚洲| 99人久久精品视频最新地址| 国产视频一区二区三区在线观看| 欧美激情亚洲综合一区| 久久精品国产成人| 一区二区三区欧美亚洲| 亚洲福利专区| 久久久久一区二区三区四区| 亚洲亚洲精品在线观看| 在线免费高清一区二区三区| 国产午夜精品一区理论片飘花| 国产精品久久7| 欧美福利电影网| 欧美在线视频观看免费网站| 亚洲美女av在线播放| 国产亚洲欧洲| 欧美性开放视频| 欧美电影免费| 久久久精品2019中文字幕神马| 中文一区二区| 99热在这里有精品免费| 欧美激情亚洲视频| 久久一区二区三区四区| 欧美在线二区| 亚洲网站视频福利| 亚洲精品在线视频观看| 国产精品美女一区二区| 欧美电影在线观看| 久久久久久电影| 欧美一区二区三区四区夜夜大片| 亚洲免费一级电影| 欧美激情导航| 欧美国产先锋| 能在线观看的日韩av| 欧美成人亚洲成人日韩成人| 亚洲欧美电影在线观看| 亚洲黄色成人久久久| 亚洲国产电影| 91久久精品一区二区三区| 在线日韩中文字幕| 亚洲国产精品传媒在线观看| 在线免费精品视频| 91久久精品久久国产性色也91| 亚洲高清在线视频| 亚洲黄色av一区| 一本色道久久综合狠狠躁篇怎么玩 | 欧美国产日韩一区二区三区| 亚洲高清一二三区| 亚洲国产成人av在线 | 欧美一二区视频| 亚洲精品日韩综合观看成人91| 99这里只有精品| 午夜精品久久久久久久久久久| 欧美高清一区| 国产精品亚洲一区二区三区在线| 国产精品午夜视频| 国产午夜精品理论片a级大结局 | 欧美风情在线观看| 欧美日韩国产精品成人| 欧美性猛交视频| 国产综合色在线| 亚洲电影自拍| 亚洲男人av电影| 麻豆久久婷婷| 亚洲精品国产精品乱码不99| 亚洲性xxxx| 久久久av毛片精品| 欧美久久精品午夜青青大伊人| 国产精品日韩欧美| 亚洲黄色在线观看| 亚洲一区二区三区在线| 狂野欧美性猛交xxxx巴西| 亚洲欧洲日韩综合二区| 香蕉久久夜色精品国产| 欧美成人国产| 国产欧美一区二区精品婷婷 | 欧美日韩伦理在线免费| 国产精品手机在线| 亚洲成色精品| 亚洲尤物在线视频观看| 你懂的国产精品| 亚洲小说春色综合另类电影| 久久久精品国产一区二区三区| 欧美日韩一区国产| 亚洲电影自拍| 欧美在线看片| 亚洲精品视频免费观看| 久久久精品一品道一区| 国产精品免费一区二区三区在线观看| **欧美日韩vr在线| 欧美在线1区| 国产精品99久久不卡二区| 久久综合电影| 国产一区二区毛片| 亚洲私人影院| 欧美顶级大胆免费视频| 亚洲欧美日韩综合| 国产精品v欧美精品v日本精品动漫| 伊伊综合在线| 久久天天躁狠狠躁夜夜av|