Jury Compromise
Time Limit:1000MS |
|
Memory Limit:65536K |
Total Submissions:23478 |
|
Accepted:6080 |
|
Special Judge |
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 #include<iostream>
using namespace std;
#define NMAX 200
int V[NMAX][2];
int MARR[25];
int N,M,mD,mP;
int MIN;
void dfs(int i,int m,int value,int valueD,int valueP){
if(m==M){
if(value<MIN){
MIN=value;
mD=valueD;
mP=valueP;
}else if(value==MIN&&valueD+valueP>mD+mP){
mD=valueD;
mP=valueP;
}
return;
}
int d=valueD+V[i][0];
int p=valueP+V[i][1];
int v=abs(d-p);
MARR[i]=1;
for(int j=1;j<=N;j++){
if(!MARR[j]){
dfs(j,m+1,v,d,p);
}
}
MARR[i]=0;
}
int main(){
MIN=25;
int i;
cin>>N>>M;
for(i=0;i<25;i++)
MARR[i]=0;
for(i=1;i<=N;i++)
cin>>V[i][0]>>V[i][1];
for(i=1;i<=N;i++)
dfs(i,0,0,0,0);
cout<<MIN<<mD<<mP<<endl;
for(i=1;i<=N;i++)
cout<<MARR[i];
}
//动态规划部分
#include<iostream>
using namespace std;
int n,m;
int dp[21][801],path[21][801];
bool select(int j,int k,int i,int*v){
while(j>0&&path[j][k]!=i){
k-=v[path[j][k]];
j--;
}
return j>0?false:true;
}
int main(){
cin>>n>>m;
int* p=new int[n+1]; //每个人的控方值
int* d=new int[n+1]; //每个人的辩方值
int* s=new int[n+1]; //每个人的辨控和
int* v=new int[n+1]; //每个人的辨控差
for(int i=1;i<=n;i++){
cin>>p[i]>>d[i];
s[i]=p[i]+d[i];
v[i]=p[i]-d[i];
}
memset(dp,-1,sizeof(dp));
memset(path,0,sizeof(path));
int fix=m*20;
dp[0][fix]=0;
for(int j=1;j<=m;j++){
for(int k=0;k<=2*fix;k++){
if(dp[j-1][k]>=0){
for(int i=1;i<=n;i++){
if(select(j-1,k,i,v)){
if(dp[j][k+v[i]]<dp[j-1][k]+s[i]){
dp[j][k+v[i]]=dp[j-1][k]+s[i];
path[j][k+v[i]]=i;
}
}
}
}
}
}
for(int k=0;k<=fix;k++){
if(dp[m][fix-k]>=0||dp[m][fix+k]>=0)
break;
}
int div=dp[m][fix-k]>dp[m][fix+k]?(fix-k):(fix+k);
cout<<(dp[m][div]+div-fix)/2<<" for prosecution and value ";
//控方总值 = (辨控和-辨控差+修正值)/2
cout<<(dp[m][div]-div+fix)/2<<" for defence:"<<endl;
}
分享到:
相关推荐
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
POJ ACM 1015 Jury Compromise 两种解法 解题报告
matlab开发-Jury。计算给定多项式的陪审团图-数字或符号。
使用Jury准则对时域有限差分算法进行稳定性分析,肖飞,唐小宏,稳定性分析是时域有限差分算法应用中重要的内容。然而,在分析过程中要找出对应特征多项式的所有的根是相当困难的,尤其是对于高
matlab开发-Jury.zip.zip
将陪审团标准视为劳斯标准(或 Hurwitz 标准)的离散时间版本如果给定多项式的系数,JURY 会计算 Jury-Chart,通过它可以决定该多项式的多少根位于单位圆盘之外。
在分析过程中要找出对应...为了解决 这个问题,控制领域中的Jury准则将被引入,它仅需要使用特征多项式的系数而不需要直接求解整个方程获得 所有的根。因此,使用它可以简化算法的稳定性分析,2个实例验证了它的有效性。
为解决单输入单输出(SISO)动态矩阵控制的鲁棒稳定问题,采用过程阶跃响应的变化界来描述模型的不确定度,利用 Jury定理推导了系统稳定的充分条件。在此基础上,对一类阶跃响应系数具有递增性质的系统,分析了具体的参数...
1303 Jury Compromise 其实不是很难,但是很容易错,555…… 1345 Best Deal 简单题,但是也很容易错……555…… 1360 Radar Installation 简单题 1396 The Umbrella Problem: 2054 简单题 1058 Currency ...
1303 Jury Compromise 其实不是很难,但是很容易错,555…… 1345 Best Deal 简单题,但是也很容易错……555…… 1360 Radar Installation 简单题 1396 The Umbrella Problem: 2054 简单题 1058 Currency ...
陪审前 如何同步? 从 gh-pages 拉取请求 基础:gh-pages > 比较:master 拉取请求 保证金交易!
适用于任意阶系统的稳定性判定,在matlab环境下编程实现的劳斯判据
包含c库插件的lua开发工具。包含c库插件的lua开发工具。包含c库插件的lua开发工具。包含c库插件的lua开发工具。包含c库插件的lua开发工具。包含c库插件的lua开发工具。
Jury 稳定性判据是一种通过分析其特征方程的系数来确定线性离散时间系统稳定性的方法。 每个操作都有广泛的动机和描述。 非常适合教学。
NWERC(西北欧赛区)题目、解答程序、数据等版权归 NWERC 2005 jury 所有。 These problem texts and solutions are copyright 2005 by the NWERC 2005 jury. They are licensed under the Creative Commons ...
NWERC(西北欧赛区)题目、解答程序、数据等版权归 NWERC 2011 jury 所有。 These problem texts and solutions are copyright 2011 by the NWERC 2011 jury. They are licensed under the Creative Commons ...
注意:DOMjudge已移至www.domjudge.org和Github进行所有开发。 DOMjudge是运行编程竞赛的自动判断系统。 团队和陪审团双方的界面都是基于Web的,还提供了命令行提交工具。 它是用PHP,shell脚本和C / C ++编写的,...
DOM法官 这是编程竞赛评审委员会系统“ DOMjudge”版本8.0.0DEV DOMjudge是一个运行编程竞赛的系统,例如ICPC地区和世界冠军编程竞赛。 文献资料 有关安装和要求的更多信息,请参阅doc / manual目录下的文档。...
NWERC(西北欧赛区)题目、解答程序、数据等版权归 NWERC 2011 jury 所有。 These problem texts and solutions are copyright 2011 by the NWERC 2011 jury. They are licensed under the Creative Commons ...
NWERC(西北欧赛区)题目、解答程序、数据等版权归 NWERC 2010 jury 所有。 These problem texts and solutions are copyright 2010 by the NWERC 2010 jury. They are licensed under the Creative Commons ...