題意：n個陪審團，每個陪審團有x,y值，選出m個陪審團，要求 （sum（xi）-sum（yi））最少，當?（sum（xi）-sum（yi））最少有多個，取sum（xi）+sum（yi）最大那個

，并順序輸出陪審團的序號

思路：先x-y,x+y存起來，再按當dp[i][j]，j相同時，要值最大，當然存路徑是最煩的。

#include <iostream> #include<cstdio> #include <cstring> #include<algorithm> using namespace std; #define N 210 int path[25][1000],map[25][1000],n,m,sub[25*10],plusa[25*10],size,ans[25]; int main(int argc, char** argv) {int i,j,k,x,y,cas=1;while(scanf("%d%d",&n,&m)!=EOF,n||m){for(i=1;i<=n;i++){scanf("%d%d",&x,&y);sub[i]=x-y;plusa[i]=x+y; }memset(map,-1,sizeof(map));memset(path,-1,sizeof(path));size=25*m;map[0][size]=0;path[0][size]=0;for(i=1;i<=n;i++){if(map[1][size+sub[i]]<plusa[i]){map[1][size+sub[i]]=plusa[i];path[1][size+sub[i]]=i;}}for(i=1;i<m;i++){for(j=0;j<2*size;j++)if(path[i][j]>=0){for(k=1;k<=n;k++){if(map[i+1][j+sub[k]]<map[i][j]+plusa[k]){for(x=i,y=j;x>=1;x--){if(path[x][y]==k)break;y-=sub[path[x][y]];}if(x<1){map[i+1][j+sub[k]]=map[i][j]+plusa[k];path[i+1][j+sub[k]]=k;}}}}}int num=0;for(i=0;i<=2*size;i++){if(map[m][size+i]>=0||map[m][size-i]>=0){if(map[m][size+i]>map[m][size-i])j=size+i;elsej=size-i;break;}}for(i=m,k=j;i>=1;i--){ans[num++]=path[i][k];k-=sub[ans[num-1]];}sort(ans,ans+num);printf("Jury #%d\n",cas++);printf("Best jury has value %d for prosecution and value %d for defence: \n",(map[m][j]+j-size)/2,(map[m][j]-(j-size))/2);for(i=0;i<num;i++){printf(" %d",ans[i]);}printf("\n");}return 0; }

轉載于:https://www.cnblogs.com/neng18/p/3676404.html

總結

以上是生活随笔為你收集整理的poj 1015 Jury Compromise_dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。