poj 1260

题意解释：

有n个等级的珠宝，等级依次升高，等级越高价钱越高，每买一个等级的任何数量的珠宝必须多付10颗此种珠宝的价钱，可以用高等级的珠宝代替低等级的，问要买到若干规定的数量和等级珠宝的最少花费。例如买5颗价值为10的、100颗价值为20的珠宝，有两种方案：一种为分别买两种等级的珠宝价钱为(5+10)*10+(100+10)*20 = 2350；另一种是将等级低的（即价格低）的珠宝全部换为等级高的，此时价钱为(5+100+10)*20 = 2300，故第二种方案较优。

解题思路：

首先需要证明一点，用高一等级的代替低一等级的必须是连续代替。例如 3 5，90 7，100 12要想代替3个5价值的首先考虑用7价值的代替，因为3*7=21 （3+10）*5=65 显然比较合算，这样就不需要考虑用12价值的那个代替了，因为前面已经有了最优解，也就是说相互代替不会跳跃。

证明这一点后开始分析，用sum[i]表示前i中珠宝总数，对于第i等级珠宝，dp[i]表示其最优解，那么dp[i]可能是(sum[i]+10) *p[i] 即前面所有的珠宝用i的价值去买，或者(sum[i]-sum[1]+10)*p[i]+dp[1] 即从第二个开始前面的所有珠宝用i的价值去买，或者（sum[i]-sum[2] +10）*p[i] + dp[2] 即从第三个。。。依次计算，其中最小的一个就是i的解。注意，上面提到的跳跃是指不用i+1等级珠价值去计算i等级以及其以下的珠宝，但可以将i以下等级的珠宝归为等级为i的价格进行计算，这样就会保证当前价值最小。这样状态方程便有dp[i]=min(dp[i],(sum[i]-sum[j]+10)*p[i]+dp[j])，（1<=j<=i）。

在写状态方程时是整体到局部的思路去考虑，具体写代码特别是边界条件时则需要自底下向上推导。通常需要将状态数组（此题为dp[]）分开处理，即先对其边界赋值，处理特殊情况，再按状态方程进行计算。

代码如下：

#include <stdio.h>
#include <string.h>
int tcase, n, a[2000], p[2000], dp[2000], sum[2000];

int min (int x, int y)
{
	return x>y?y:x;
}

int main ()
{
	int i, j;
	scanf("%d", &tcase);
	while(tcase--)
	{
		memset(dp, 0, sizeof(dp));
		sum[0] = 0;
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d%d", &a[i], &p[i]);
			sum[i] = sum[i-1] + a[i];
			dp[i] = (sum[i]+10) * p[i];
		} // 数组临界预处理。
		for (i = 1; i <= n; i++)
			for (j = 1; j <= i; j++)
				dp[i] = min (dp[i], (sum[i]-sum[j]+10)*p[i] + dp[j]);
			// 根据状态转移方程计算数组。
			// 此处取最小值的方法较巧妙，值得学习。
			printf("%d\n", dp[n]);
	}
	return 0;
}