#include <stdio.h>
#include <memory.h>

struct Pearl
{
	int prize;
	int nbuy;
};

Pearl allPearl[105];
int dp[105];
int nPearl;

int main()
{
	int ncase;

	scanf("%d", &ncase);

	while(ncase--)
	{
		scanf("%d", &nPearl);

		for( int i = 0; i < nPearl; i++)
		{
			scanf("%d%d", &allPearl[i].nbuy, &allPearl[i].prize);
		}

		dp[nPearl - 1] = allPearl[nPearl - 1].nbuy;
		int replace, minPrize = 100000000;


		int sum = (dp[nPearl - 1] + 10) * allPearl[nPearl-1].prize;


		for( int i = nPearl - 2; i >= 0; i--)
		{
			dp[i] = 0;
			minPrize = 100000000;

			for( int j = nPearl - 1; j >= i; j--)
			{
				int prize;
				if(dp[j] == 0)
				{
					prize = sum + (allPearl[i].nbuy + 10) * allPearl[j].prize;
				}
				else
				{
					prize = sum + (allPearl[i].nbuy ) * allPearl[j].prize;
				}
				
				if(prize < minPrize)
				{
					minPrize = prize;
					replace = j;
				}
			}
			dp[replace] += allPearl[i].nbuy;
			sum = minPrize;
		}
		

		printf("%d\n", sum);
	}

}

• Re:这种做法是错误的！！ (82) 058179 2013-03-20 22:06:39