找了一个AC的程序比了一下，有些例子虽然选择不一样，但是两个都是正确的，为什么这个程序就不能AC呢？
请高手解答一下.

#include <stdio.h>

#define MAX 500
#define MM 21

struct p_s{
	int p[7]; // 最多200个人 200/32 + 1
};
void ps_add(p_s *ps, int idx)
{
	int i = idx/32;
	ps->p[i] |= (1<<(idx%32));
}
void ps_set(p_s *ps, int idx)
{
	int i;
	for(i = 0; i < 7; i++)
		ps->p[i] = 0;
	i = idx/32;
	ps->p[i] = (1<<(idx%32));
}
void ps_cpy(p_s *to, p_s *from)
{
	for(int i = 0; i < 7; i++)
		to->p[i] = from->p[i];
}
int ps_dul(p_s *ps, int idx)
{
	int i = idx/32;
	return (ps->p[i] & (1<<(idx%32)));
}
// SUM[m][k]表示选择m个人，其d - p + MAX = k时的d + p值
// 没有则置0
// PP纪录选择m个人，其d - p + MAX = k时的人编号(1 ~ 20)
int SUM[MM][MAX + MAX], A[201][2];
p_s PP[MM][MAX + MAX];

int iN, iM;
void DP()
{
	int m, i, j, v, w;
	int vmax, vmin;
	// 清空信息
	for(i = 0; i <= iM; i++){
		for(j = 0; j < MAX + MAX; j++){
			SUM[i][j] = 0;
			for(int k = 0; k < 7; k++)
				PP[i][j].p[k] = 0;
		}
	}
	vmax = vmin = MAX;
	for(m = 1; m <= iM; m++){ // 选择1 ~ iM个人
		int t1 = vmax, t2 = vmin;
		for(i = 1; i <= iN; i++){ // 遍历iN个人
			for(j = vmin; j <= vmax; j++){ // m - 1个人时d - p是(vmin ~ vmax)
				if(ps_dul(&PP[m - 1][j], i)) continue; // 已选择i
				if(m - 1 && SUM[m - 1][j] == 0) continue;
				v = A[i][1] - A[i][0]; // d - p
				w = A[i][1] + A[i][0]; // d + p
				v = v + j;
				// 选择一个人后d - p由j变为v
				if(SUM[m][v] < SUM[m - 1][j] + w){// 是否可以更新
					SUM[m][v] = SUM[m - 1][j] + w;
					ps_cpy(&PP[m][v], &PP[m - 1][j]);
					ps_add(&PP[m][v], i);
				}
				// 更新t1, t2 | m个人时的上下限
				if(t1 < v) t1 = v;
				if(t2 > v) t2 = v;
			}
		}
		vmax = t1;
		vmin = t2;
	}
}
int main()
{
	int i, d, p, icase;
	for(icase = 1; ; icase++){
		scanf("%d %d", &iN, &iM);
		if(iM == 0 || iN == 0) break;
		for(i = 1; i <= iN; i++){
			scanf("%d %d", &A[i][0], &A[i][1]);
		}
		DP();
		// 找到的(d - p)
		int sum = 0, dif = MAX - 1;
		for(i = 0; i < MAX; i++){// d - p为正
			if(sum = SUM[iM][MAX + i]){
				dif = i;
				break;
			}
		}
		for(i = 0; i <= dif; i++){// d - p为负
			if(SUM[iM][MAX - i]){
				if(i < dif || (sum < SUM[iM][MAX - i])){
					sum = SUM[iM][MAX - i];
					dif = -i;
				}
				break;
			}
		}
		d = (sum + dif)/2;
		p = (sum - dif)/2;
		printf("Jury #%d\n", icase);
		printf("Best jury has value %d for prosecution and value %d for defence:\n",
			p, d);

		for(p = 0; p < 7; p++){
			d = 1;
			for(i = 0; i < 32; i++){
				if(PP[iM][dif + MAX].p[p] & d) printf(" %d", i + p*32);
				d <<= 1;
			}
		}
		printf("\n\n");
	}
	return 0;
}

• Re:不明白了，这样就不行 (2563) sparkling 2007-06-30 10:07:06