社区讨论

求助,输出方案

UVA323Jury Compromise参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lobwlhgf
此快照首次捕获于
2023/10/30 04:08
2 年前
此快照最后确认于
2023/11/04 09:12
2 年前
查看原帖
CPP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 255, M = 35;

struct rec
{
  int w1, w2;
} man[N];
int n, m;
int f[N][M][450];
vector<int> ans;

int main()
{
	int Case = 0;
	while(scanf("%d%d", &n, &m) == 2, n || m)
	{
	  ans.clear();
	  memset(man, 0, sizeof man);
	  for(int i = 1; i <= n; i ++) 
	    scanf("%d%d", &man[i].w1, &man[i].w2);
	  memset(f, 0x3f, sizeof f);
	  f[0][0][0] = 0;
	  for(int i = 1; i <= n; i ++)
	    for(int j = 0; j <= m; j ++)
	      for(int k = 0; k <= 400; k ++)
	      {
	        f[i][j][k] = f[i-1][j][k];
	        if(j > 0 && k >= man[i].w1+man[i].w2 && abs(f[i][j][k]) >= abs(f[i-1][j-1][k-man[i].w1-man[i].w2] + man[i].w1 - man[i].w2))
	        {
	          f[i][j][k] = f[i-1][j-1][k-man[i].w1-man[i].w2]+man[i].w1-man[i].w2;
	        }
	       // if(f[i][j][k] <= 0x3f3f3f3f/2) printf("f[%d][%d][%d] = %d\n", i, j, k, f[i][j][k]);
	      }
	  int dx = 0x3f3f3f3f, sum = 0;
	  for(int i = n; i >= 0; i --)
	    for(int j = 400; j >= 0; j --)
	      if(abs(dx) > abs(f[i][m][j]) || (abs(dx) == abs(f[i][m][j]) && j > sum))
	      {
	        dx = f[i][m][j];
	        sum = j;
	      }
	  int p = dx+sum>>1, d = sum-p;
	  printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++ Case, p, d);
	  for(int i = m; i <= n; i ++)
	    if(f[i][m][sum] == dx) 
	    {
	      n = i;
	      break;
	    }
	  for(int i = n, j = m; i >= 1 && j; i --)
	  {
	    if(f[i][j][sum] == dx && sum >= man[i].w1-man[i].w2 && f[i-1][j-1][sum-man[i].w1-man[i].w2]+man[i].w1-man[i].w2 == dx)
	    {
	      ans.push_back(i);
	      dx = dx-man[i].w1+man[i].w2;
	      sum = sum-man[i].w1-man[i].w2;
	      j --;
	    }
	  }
	  for(int i = ans.size()-1; i >= 0; i --)
	    printf(" %d", ans[i]);
	  cout << endl << endl;
	}
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...