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

时间：2023-03-08 23:42:34
【题解】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了不要直接拍，要先看看代码里有没有粗心或者逻辑错误

相关文章