2722854_tle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 49 行

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
	int i, n, d, t;
	int ca, cb;
	int wa, wb;
	int w[11], c[11], ans;
	int a[] = {0,1,2,3,4,5,6,7,8,9,10};

	scanf("%d%d",&n,&d);
	for (i = 0; i < n; i++)
		scanf("%d%d",&w[i],&c[i]);
	ans = -1;
	do
	{
		t = ca = cb = wa = wb = i =0;
		while(i<n)
		{
			if(!t)
			{
				while(i<n&&wa-wb<=d)
				{
					wa += w[a[i]];
					ca += c[a[i]];
					i++;
				}
				t = 1;
			}
			else
			{
				while(i<n&&wb-wa<=d)
				{
					wb += w[a[i]];
					cb += c[a[i]];
					i++;
				}
				t = 0;
			}
		}
		if (cb > ans)
			ans = cb;
	}while(next_permutation(a,a+n));
	printf("%d\n",ans);
	return 0;
}