【题解】Jury Compromise(链表+DP)

【题解】Jury Compromise(链表+DP)

传送门

题目大意

给你\(n\le 200\)个元素,一个元素有两个特征值,\(c_i\)和\(d_i\),\(c,d \in [0,20]\),现在请你选出\(m\le 20\)个元素使得\(\sum c+\sum d\)最大,使得$|\sum c - \sum d|最小,输出\sum c \(和\)\sum d$和一组合法方案。

分析

是DP无误了。

我们可以先不考虑绝对值,平移一下值域,假如说我们知道\(\sum c +- \sum d\)就可以通过解方程解出来\(\sum c\)和\(\sum d\)了,考虑设置状态:

  • 要考虑\(m\)的限制,所以要把已经选择了多少元素记录在状态里面。
  • 要考虑\(|\sum c - \sum d|\),有绝对值不好考虑,有两个转移的方向,所以我们考虑直接把绝对值里面的值记录到状态里,也不大,\(8000\)而已。
  • 这个时候,只要考虑\(\sum c + \sum d 最大,直接DP\)

\(dp(i,j)\)表示选取了\(i\)个数之后,绝对值里面的值是\(j\)的最大的\(c_i+d_i\)为多少,转移:

\[t\text{第t个元素}:dp(i,j)=max\{dp(i-1,k-(d[t]-c[t]))\}
\]

然而我们还要记录方案,我们直接用链表,由于对于每个\((t,i,j)\),只会在链表中增加一个元素,所以空间没有问题,你输出vector的size发现只有四千多。

写得很心酸,但是还是放没有调试信息的代码出来。

最后输出方案链表操作即可。代码里的reverse是trick,因为要求方案从小往大输出。还有因为用过很多种办法,所以导致代码有无用的冗余。

但其实我是暴力过此题(时间/空间/代码长度)(笑)

【题解】Jury Compromise(链表+DP)

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector> using namespace std; typedef long long ll;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(c<48||c>57)f|=c==45,c=getchar();
while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
} struct NODE{
int data;
NODE(){data=0;}
inline void clean(){
data=-0x3f3f3f;
}
}; struct DATA{
NODE data[8000+1];
inline NODE&operator[](int x){return data[x+4000];}
inline void clean(){
for(register int t=0;t<=8000;++t)
data[t].clean();
}
}dp[21]; int way[21][8000+1];
int n,m; struct E{
int data,nx;
E(){data=nx=0;}
}T;
vector < E > e;
inline void add(int&fr,int to,int data){
register E temp;
temp.data=data;
temp.nx=to;
e.push_back(temp);
fr=e.size()-1;
}
int p[201],d[201]; int main(){
int cnt=0;
while(n=qr(),m=qr(),n or m){
e.clear();
e.push_back(T);
memset(way,0,sizeof way);
for(register int t=1;t<=n;++t) p[t]=qr(),d[t]=qr();
for(register int t=0;t<=20;++t) dp[t].clean();
reverse(p+1,p+n+1),reverse(d+1,d+n+1);
dp[0][0].data=0;
for(register int t=1,delta;t<=n;++t){
delta=p[t]-d[t];
for(register int i=min(m,t)-1;i>=0;--i){
for(register int k=max(-4000,-4000+delta),edd=min(4000,4000-delta);k<=edd;++k){
NODE& fr=dp[i][k];
NODE& to=dp[i+1][k+delta];
if(fr.data>=0&&to.data<fr.data+p[t]+d[t])
to.data=fr.data+p[t]+d[t],add(way[i+1][k+delta+4000],way[i][k+4000],t);
}
}
} register int t1,t2,cur=0;
for(register int t=0;t<=4000;++t){
if(dp[m][t].data>=0||dp[m][-t].data>=0){
if(dp[m][t].data<dp[m][-t].data) t=-t;
cur=t;
t1=(dp[m][t].data-t)>>1;
t2=(dp[m][t].data+t)>>1;
break;
}
}
printf("Jury #%d \nBest jury has value %d for prosecution and value %d for defence:\n",++cnt,t2,t1);
for(register int t=way[m][cur+4000];t;t=e[t].nx)
printf(" %d",n-e[t].data+1);
putchar('\n'),putchar('\n');
}
return 0;
}
  致看我这道题代码的同学:

  本份代码历经一次编写,三次重构,最终剩下3.5k 实际上写了 10k以上

  算法使用过:套bitset 套vector 都tle了 现在用的是链表

  为了调试,本人从网上蒯了std 并且写了特制的check.cpp make.cpp 还有spj.cpp check+spj=5k

  最终发现是自己想压行却少分类讨论了一种情况

  请同学们代码WA了不要直接拍,要先看看代码里有没有粗心或者逻辑错误
上一篇:coreCLR系列随笔 之ClrJit项目之alloc.cpp文件分析(1)


下一篇:vue 中注册全局组件