Jury Compromise

心已赠人 2022-01-08 00:25 188阅读 0赞

[Jury Compromise][]

有n对数，每对数由\\((d\_i,p\_i)\\)组成，现在要求选出m对数，\\(\\sum\\)表示对这m对数中的元素累加,在\\(|\\sum d\_i-\\sum p\_i|\\)最小的前提下，保证\\(\\sum d\_i+\\sum p\_i\\)最大，，输出\\(\\sum d\_i,\\sum p\_i\\),\\(1<=n<=200, 1<=m<=20,d\_i\\leq 20,p\_i\\leq 20\\)。

### 解 ###

对于绝对值问题，常采取去绝对值的方法，如波浪，就是采取递增填排列，忽略了绝对值的影响，或者是直接可以进行转移，如making grade。

此处肯定要以处理到哪一对数为阶段，两个阶段之间存在影响，故无法去绝对值，但是注意到数据范围很小，于是a我们可以直接转移绝对值，于是不难想到\\(f\[i\]\[j\]\[k\]\\)表示考虑到第i对数，已经选了j对数，\\(\\sum d\_i-\\sum p\_i\\)为k的最大的\\(\\sum d\_i+\\sum p\_i\\)，于是不难有转移

\\\[f\[i\]\[j\]\[k\]=\\max(f\[i-1\]\[j\]\[k\],f\[i-1\]\[j-1\]\[k-(d\_i-p\_i)\]+d\_i+p\_i)\\\]

边界：\\(f\[0\]\[0\]\[0\]=0\\),其余负无限大

答案：\\(f\[n\]\[m\]\[d\]\\),\\(|d|\\)尽可能小

而且注意到第一维可以丢掉，类似背包，再进行倒序枚举即可。

参考代码：

未压维

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register using namespace std; int dp[201][21][901],pre[201][21][901], d[201],p[201]; template<class free> il free Max(free,free); il void print(int,int,int); int main(){ int n,m,tot(0); while(scanf("%d%d",&n,&m),n,m){ for(ri int i(1);i<=n;++i) scanf("%d%d",&d[i],&p[i]); memset(dp,-127,sizeof(dp)),memset(pre,0,sizeof(pre)); dp[0][0][450]=0; for(ri int i(1),j,k;i<=n;++i){ for(k=0;k<=900;++k)dp[i][0][k]=dp[i-1][0][k]; for(j=1;j<=m;++j) for(k=0;k<=900;++k) if(k-(d[i]-p[i])>=0&&k-(d[i]-p[i])<=900){ dp[i][j][k]=dp[i-1][j][k]; if(dp[i-1][j-1][k-(d[i]-p[i])]+d[i]+p[i]>dp[i][j][k]) dp[i][j][k]=dp[i-1][j-1][k-(d[i]-p[i])]+d[i]+p[i],pre[i][j][k]=1; } }int ans(0); for(ri int i(450);i<=900;++i) if(dp[n][m][i]>=0||dp[n][m][900-i]>=0){ if(dp[n][m][i]>dp[n][m][900-i])ans=i; else ans=900-i; break; } printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++tot,dp[n][m][ans]+ans-450>>1,dp[n][m][ans]-(dp[n][m][ans]+ans-450>>1)); print(n,m,ans),putchar('\n'),putchar('\n'); } return 0; } il void print(int a,int b,int c){ if(!a||!b||!c)return; if(pre[a][b][c]){ print(a-1,b-1,c-(d[a]-p[a])); printf("%d ",a); } else print(a-1,b,c); } template<class free> il free Max(free a,free b){ return a>b?a:b; }

压了维

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register using namespace std; bool pre[201][21][901]; int d[201],p[201],dp[21][901]; void print(int,int,int); int main(){ int n,m,i,j,k,tot(0); while(scanf("%d%d",&n,&m),n&&m){ memset(pre,0,sizeof(pre)); memset(dp,-127,sizeof(dp)); dp[0][450]=0; for(i=1;i<=n;++i){ scanf("%d%d",&d[i],&p[i]); for(j=m;j;--j) for(k=0;k<=900;++k){ if(k-(d[i]-p[i])<0||k-(d[i]-p[i])>900)continue; if(dp[j-1][k-(d[i]-p[i])]+d[i]+p[i]>dp[j][k]) dp[j][k]=dp[j-1][k-(d[i]-p[i])]+d[i]+p[i],pre[i][j][k]|=true; } } for(j=450;j<=900;++j) if(dp[m][j]>=0||dp[m][900-j]>=0){ if(dp[m][j]>dp[m][900-j])i=j; else i=900-j; break; }j=dp[m][i]+i-450>>1,k=dp[m][i]-j; printf("Jury #%d\nBest jury has value %d for prosec" "ution and value %d for defence:\n",++tot,j,k), print(n,m,i),putchar('\n'),putchar('\n'); } return 0; } void print(int a,int b,int c){ if(!a||!b)return; if(pre[a][b][c]) print(a-1,b-1,c-(d[a]-p[a])), printf(" %d",a); else print(a-1,b,c); }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10917485.html

[Jury Compromise]: https://www.luogu.org/problemnew/show/UVA323