【题解】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，因为要求方案从小往大输出。还有因为用过很多种办法，所以导致代码有无用的冗余。
但其实我是暴力过此题(时间/空间/代码长度)(笑)
//@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了不要直接拍，要先看看代码里有没有粗心或者逻辑错误