【题解】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，因为要求方案从小往大输出。还有因为用过很多种办法，所以导致代码有无用的冗余。

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

//@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了不要直接拍，要先看看代码里有没有粗心或者逻辑错误