#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
//PKU 1015
/*
4 2
1 2
2 3
4 1
6 2
0 0
*/
#define NMAX 202
#define MMAX 852
#define XMAX 22
#define PB push_back
typedef struct man
{
bool f;//是否存在
int sum;//和
vector <int> a;//哪些人被选中
}man;
int p[NMAX];
int d[NMAX];
man state[2][XMAX][MMAX];//man[i][j][k],从前i个人里选j个人,k=p[]-d[]+400;
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
bool cmp(int a,int b)
{
return a<b;
}
void cal(int nnum,int mnum)
{
int i,j,k,mmin,mmax,tt,pre,now,smax,tk,ps,ds,t,choose;
int cha[NMAX];
vector<int>::iterator iter;
for(i=0;i<=1;i++)
{
for(j=0;j<XMAX;j++)
{
for(k=0;k<MMAX;k++)
{
state[i][j][k].f=false;
state[i][j][k].sum=0;
state[i][j][k].a.clear();
}
}
}
for(i=1;i<=nnum;i++)
cha[i]=p[i]-d[i];
sort(cha+1,cha+1+nnum,cmp);
tt=0;
for(i=1;i<=mnum;i++) tt+=cha[i];
mmin=tt;
tt=0;
for(i=nnum;i>nnum-mnum;i--) tt+=cha[i];
mmax=tt;
for(i=1;i<=nnum;i++)
cha[i]=p[i]-d[i];
pre=1;
now=0;
state[0][1][cha[1]+400].f=true;
state[0][1][cha[1]+400].sum=p[1]+d[1];
state[0][1][cha[1]+400].a.PB(1);
state[0][0][400].f=true;
state[1][0][400].f=true;
for(i=2;i<=nnum;i++)
{
now=pre;
pre=(pre+1)%2;
for(j=1;j<=mnum && j<=i;j++)
{
for(k=0;k<=800;k++)
{
if(state[pre][j][k].f==true ||(k-cha[i]>=0 &&state[pre][j-1][k-cha[i]].f==true))
{ //如果不选第i个人,选前面j个人,或选第i个人,选前面j-1人的情况成立
state[now][j][k].f=true;
if((state[pre][j][k].f==true && state[pre][j-1][k-cha[i]].f==true && state[pre][j][k].sum>=state[pre][j-1][k-cha[i]].sum+p[i]+d[i] )|| (state[pre][j][k].f==true && state[pre][j-1][k-cha[i]].f==false))
{ //选第i个人,选前面j-1人的这种情况不成立,或这种情况成立但不合算
state[now][j][k].sum=state[pre][j][k].sum;
choose=1;
}
else
{
state[now][j][k].sum=state[pre][j-1][k-cha[i]].sum+p[i]+d[i];
choose=2;
}
if(choose==2)
{
state[now][j][k].a=state[pre][j-1][k-cha[i]].a;
state[now][j][k].a.PB(i);
}
else
state[now][j][k].a=state[pre][j][k].a;
}
}
}
}
tt=10000;
smax=0;
for(k=mmin+400;k<=mmax+400;k++)
{
if((tt>abs(k-400) && state[now][mnum][k].f==true)|| ( tt==abs(k-400) && smax<state[now][mnum][k].sum))
{
tt=abs(k-400);
smax=state[now][mnum][k].sum;
tk=k;
}
}
ps=ds=0;
for(iter=state[now][mnum][tk].a.begin();iter!=state[now][mnum][tk].a.end();iter++)
{
ps+=p[*iter];
ds+=d[*iter];
}
printf("Best jury has value %d for prosecution and value %d for defence: \n",ps,ds);
for(iter=state[now][mnum][tk].a.begin();iter!=state[now][mnum][tk].a.end();iter++)
{
printf("%d ",*iter);
}
}
int main()
{
int nnum,mnum,ii=0,i,psum=0,dsum=0;
scanf("%d %d",&nnum,&mnum);
while(!(nnum==0 && mnum==0))
{
for(i=1;i<=nnum;i++)
{
scanf("%d %d",&p[i],&d[i]);
}
printf("Jury #%d\n",++ii);
cal(nnum,mnum);
printf("\n\n");
scanf("%d %d",&nnum,&mnum);
}
return 0;
}
dp.rar_DP_visual c
版权申诉
193 浏览量
2022-09-22
18:24:46
上传
评论
收藏 26KB RAR 举报
朱moyimi
- 粉丝: 60
- 资源: 1万+
最新资源
- push_version
- 软件自制图像批量压缩工具
- 基于深度学习的抗梯度噪声的缺陷检测器python源码+文档说明+模型的预训练
- 基于python+pytorch+mysql实现停车场车牌识别管理系统源码+文档说明
- 基于QT+MySQl+OpenCV车牌识别搭建停车场管理系统C++源码+文档说明+界面展示
- 基于深度学习的停车场收费系统-车牌识别模块python源码+文档说明+博客教学
- 空白.pages
- 基于Java+Springboot+vue的智能停车场管理系统(源代码+数据库+9000字论文) 本项目前后端不分离+部署教程
- 基于SSM写的停车场管理系统,加入了车牌识别和数据分析+源码+文档说明
- stream-response.txt
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈