论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-07-27 15:01 |只看该作者 |倒序浏览

pku 1015 Jury Compromise
http://acm.pku.edu.cn/JudgeOnline/problem?id=1015

下面是我的代码，我是用动态规划做的，我自己测试的答案也是对的，但是它老说我Wrong Answer!到底是哪里错了？

#include <stdio.h>
#include <limits.h>

#define N 202
#define M 22

int d[N + 1], p[N + 1];
int f[N + 1][M + 1];
int S[N + 1][M + 1];
int l[N + 1][M + 1];
int n, m;
int times = 0;

void dp() {
int i, j, x1, x2, y1, y2;

for(i = 0; i <= n; i++) {
      f[i][0] = 0;
      S[i][0] = 0;
}
for(j = 1; j <= m; j++)
      for(i = 0; i < j; i++)
         f[i][j] = INT_MAX;

for(i = 1; i <= n; i++)
      for(j = 1; j <= i && j <= m; j++) {
         x1 = f[i - 1][j];
         x2 = f[i - 1][j - 1] + (d[i] - p[i]);
         y1 = x1 > 0 ? x1 : (-1) * x1;
         y2 = x2 > 0 ? x2 : (-1) * x2;
         if(y1 < y2) {
            f[i][j] = x1;
            S[i][j] = S[i - 1][j];
            l[i][j] = 0;
         }
         else if(y1 > y2) {
            f[i][j] = x2;
            S[i][j] = S[i - 1][j - 1] + d[i] + p[i];
            l[i][j] = 1;
         }
         else if(S[i - 1][j] >= S[i - 1][j - 1] + d[i] + p[i]) {
            f[i][j] = x1;
            S[i][j] = S[i - 1][j];
            l[i][j] = 0;
         }
         else {
            f[i][j] = x2;
            S[i][j] = S[i - 1][j - 1] + d[i] + p[i];
            l[i][j] = 1;
         }
      }
}

int init() {
int i;

scanf("%d%d", &n, &m);
if(n == 0 && m == 0)
      return 0;
times++;
for(i = 1; i <= n; i++) {
      scanf("%d%d", &p[i], &d[i]);
}
return 1;
}
int show_arr[N + 1];
int *show_p;
void show() {
int i, j, t, A, B, *cp;

printf("Jury #%d\n", times);

show_p = show_arr;
i = n;
j = m;
t = l[n][m];
while(j > 0) {
      if(t) {
         *show_p++ = i;
         j--;
      }
      i--;
      t = l[i][j];
}

A = B = 0;
for(cp = show_p - 1; cp >= show_arr; cp--) {
      A += d[*cp];
      B += p[*cp];
}
printf("Best jury has value %d for prosecution and value %d for defence:\n"
         , B, A);
while(show_p > show_arr) {
      printf(" %d", *--show_p);
}
printf("\n");
}

int main() {

while(init()){
      dp();
      show();
}

return 0;
}